From c4431d19cc5ddaae29d22c8c56366b53b0bad352 Mon Sep 17 00:00:00 2001
From: adam <adam@megacz.com>
Date: Wed, 4 Jan 2006 07:20:02 -0500
Subject: [PATCH] checkpoint

darcs-hash:20060104122002-5007d-e3168202afb862d070042071ceb1950df4d4549c.gz
---
 TODO                                          |   14 ++++++++++++++
 src/edu/berkeley/sbp/GSS.java                 |    5 ++---
 src/edu/berkeley/sbp/Parser.java              |    1 +
 src/edu/berkeley/sbp/util/FastSet.java        |    7 ++++---
 src/edu/berkeley/sbp/util/TopologicalBag.java |    7 +++++++
 5 files changed, 28 insertions(+), 6 deletions(-)

diff --git a/TODO b/TODO
index 5f5e1cf..3e67a2e 100644
--- a/TODO
+++ b/TODO
@@ -1,6 +1,20 @@
 _____________________________________________________________________________
 Immediately
 
+  - Performance
+
+     - Next target: TopologicalBag (make it wickedfast: preoptimize)
+
+     - Forest: keep() and valid() -- can we do this with states
+       rather than subtrees?
+
+     - hash Long->long: it's all bogus
+
+  * huge performance improvement (try for more)
+  * pick back up cleaning up end of Parser.java (Reduction)
+  * some weird edge cases; check last regression test, 'make doc'
+
+
   - Sensible tree-printout
   - make Tib.Block extend Tree<>
 
diff --git a/src/edu/berkeley/sbp/GSS.java b/src/edu/berkeley/sbp/GSS.java
index 0bc14ae..645fa8f 100644
--- a/src/edu/berkeley/sbp/GSS.java
+++ b/src/edu/berkeley/sbp/GSS.java
@@ -92,8 +92,7 @@ class GSS {
                 if (token==null) break;
                 int count = 0;
                 Parser.Table.Reduction r = null;
-                for(Parser.Table.Reduction red : token==null ? state.getEofReductions() : state.getReductions(token)) { r = red; count++; }
-                if (count==0) return;     // BEWARE! this optimization is suspected to cause really nasty heisenbugs
+                if (!state.hasReductions(token)) return;
                 //if (count > 1) break;
                 //if (r.numPop == 0) break;
                 //r.reduce(pending, parent, null, Phase.this, null);
@@ -223,7 +222,7 @@ class GSS {
             private Node(Node parent, Forest pending, Parser.Table.State state, Phase start) {
                 this.state = state;
                 if (pending != null) this.holder().merge(pending);
-                if (parent != null) parents().add(parent, true);
+                if (parent != null) parents().add(parent);
                 if (Phase.this.hash.get(code(state, start)) != null) throw new Error("severe problem!");
                 Phase.this.hash.put(code(state, start), this);
                 Phase.this.numNodes++;
diff --git a/src/edu/berkeley/sbp/Parser.java b/src/edu/berkeley/sbp/Parser.java
index 868b200..5c399cc 100644
--- a/src/edu/berkeley/sbp/Parser.java
+++ b/src/edu/berkeley/sbp/Parser.java
@@ -185,6 +185,7 @@ public abstract class Parser<T extends Token, R> {
             public Iterable<State>     getShifts(Token t)          { return shifts.get(t); }
             public boolean             isAccepting()               { return accept; }
             public Iterable<Reduction> getReductions(Token t)      { return t==null ? eofReductions : reductions.get(t); }
+            public boolean             hasReductions(Token t)      { return t==null ? eofReductions.size()>0 : reductions.has(t); }
             public Iterable<Reduction> getEofReductions()          { return eofReductions; }
             public Iterator<Position>  iterator()                  { return hs.iterator(); }
 
diff --git a/src/edu/berkeley/sbp/util/FastSet.java b/src/edu/berkeley/sbp/util/FastSet.java
index d3be774..bdfa380 100644
--- a/src/edu/berkeley/sbp/util/FastSet.java
+++ b/src/edu/berkeley/sbp/util/FastSet.java
@@ -3,9 +3,9 @@ import java.util.*;
 
 public /*final*/ class FastSet<T> implements Iterator<T>, Iterable<T> {
 
-    public static final int INITIAL_SIZE = 128;
+    public static final int INITIAL_SIZE = 8;
 
-    private       Object[] array;
+    private       Object[] array = null;
     private       T        only  = null;
     private       int      i     = -1;
     private       int      size  = 0;
@@ -39,7 +39,8 @@ public /*final*/ class FastSet<T> implements Iterator<T>, Iterable<T> {
         }
     }
     public void add(T t, boolean check) {
-        if (check) for(Object o : this) if (o.equals(t)) return;
+        //if (check) for(Object o : this) if (o.equals(t)) return;
+        if (check) for(Object o : this) if (o==t) return;
         add(t);
     }
     public void add(T t) {
diff --git a/src/edu/berkeley/sbp/util/TopologicalBag.java b/src/edu/berkeley/sbp/util/TopologicalBag.java
index 8862be6..cdbe976 100644
--- a/src/edu/berkeley/sbp/util/TopologicalBag.java
+++ b/src/edu/berkeley/sbp/util/TopologicalBag.java
@@ -91,6 +91,13 @@ public class TopologicalBag<K,V> implements MapBag<Topology<K>,V> {
         return false;
     }
 
+    public boolean has(K k) {
+        for(Topology<K> t : h.keySet())
+            if (t.contains(k) && !h.get(t).isEmpty())
+                return true;
+        return false;
+    }
+
     private HashMap<K,Iterable<V>> cache = new HashMap<K,Iterable<V>>();
     public Iterable<V> getAll(Topology<K> k) { return h.get(k); }
     public Iterable<V> get(K k) {
-- 
1.7.10.4