jscheme-user

[Jscheme-user] DynamicVariable proposal

[Ken A. <kan...@bb...>]

Tim,
Let me know what you think of this proposal.  

Currently a DynamicVariable has 3 fields
Symbol name
DynamicEnvironment dynamicenv - used to look up value in hash table.
Object storedDynamicValue         - only used during serialization.

A DynamicEnvironment, DE, maps symbols to values.
So every time we evaluate a DV, we do a hash lookup.

I'd like to propose we 
1. put the DV's value in the storedDynamicValue field 
2. remove the dynamicenv field.
3. Change DE to map from Symbol -> DV.
This means the DE will intern the DV for a symbol, but it can use its current hashtable to do that.  getBindings and importBindings would have to clone all the DV's (or could they be shared?).

The advantage is we'd get rid of a runtime hash lookup for every global value.

How does that sound?

k

Re: [Jscheme-user] DynamicVariable proposal

[Timothy J. H. <tim...@ma...>]

On Jul 9, 2004, at 2:55 PM, Ken Anderson wrote:

> Tim,
> Let me know what you think of this proposal.
>
> Currently a DynamicVariable has 3 fields
> Symbol name
> DynamicEnvironment dynamicenv - used to look up value in hash table.
> Object storedDynamicValue         - only used during serialization.
>
> A DynamicEnvironment, DE, maps symbols to values.
> So every time we evaluate a DV, we do a hash lookup.
>
> I'd like to propose we
> 1. put the DV's value in the storedDynamicValue field
> 2. remove the dynamicenv field.
> 3. Change DE to map from Symbol -> DV.
I agree. I'd thought about this optimization before and it makes great 
sense.

> This means the DE will intern the DV for a symbol, but it can use its 
> current hashtable to do that.  getBindings and importBindings would 
> have to clone all the DV's (or could they be shared?).
I think they could be shared. Modules are assumed to be locked (i.e. 
you can't change the bindings
of toplevel symbols) and so there would be no need to clone.
>
> The advantage is we'd get rid of a runtime hash lookup for every 
> global value.
Yes. I tried to see whether this would make a dramatic difference by 
comparing two
expressions which differ only in their use of globally defined symbols:

 > (define fib
    (lambda (n)
        (if (< n 3) 1 (+ 1 (fib (- n 1)) (fib (- n 2))))))

 > (define fib2
   (let ((+ +) (- -) (< <))
    (lambda(n)
      (if (< n 3) 1 (+ 1 (fib (- n 1)) (fib (- n 2)))))))

 > (time (fib  25) 1)
(150049 (986 msec) (20776 bytes))

 > (time (fib2 25) 1)
(150049 (916 msec) (3288 bytes))

Here the code in the closure of fib2 uses only local variables
and hence should be doing four fewer hash table lookups for
each procedure call, but I don't see much in the way of time
differences....

I really expected a bigger time difference. The regular approach gets
152K procedure calls per second (on a Powerbook G4 with jdk1.4)
and the fancier approach gets 163K pc/sec which is about a 7% 
improvement.

---Tim---

Re: [Jscheme-user] DynamicVariable proposal

[Ken A. <kan...@bb...>]

I just made the changes for this.
The Gabriel benchmarks show a 3% improvement.
I should have tried your benchmark.

Toby,
Can you test serialization and see if your patch is still needed.

k

At 11:08 PM 7/15/2004 -0400, Timothy John Hickey wrote:

>On Jul 9, 2004, at 2:55 PM, Ken Anderson wrote:
>
>>Tim,
>>Let me know what you think of this proposal.
>>
>>Currently a DynamicVariable has 3 fields
>>Symbol name
>>DynamicEnvironment dynamicenv - used to look up value in hash table.
>>Object storedDynamicValue         - only used during serialization.
>>
>>A DynamicEnvironment, DE, maps symbols to values.
>>So every time we evaluate a DV, we do a hash lookup.
>>
>>I'd like to propose we
>>1. put the DV's value in the storedDynamicValue field
>>2. remove the dynamicenv field.
>>3. Change DE to map from Symbol -> DV.
>I agree. I'd thought about this optimization before and it makes great sense.
>
>>This means the DE will intern the DV for a symbol, but it can use its current hashtable to do that.  getBindings and importBindings would have to clone all the DV's (or could they be shared?).
>I think they could be shared. Modules are assumed to be locked (i.e. you can't change the bindings
>of toplevel symbols) and so there would be no need to clone.
>>
>>The advantage is we'd get rid of a runtime hash lookup for every global value.
>Yes. I tried to see whether this would make a dramatic difference by comparing two
>expressions which differ only in their use of globally defined symbols:
>
>> (define fib
>   (lambda (n)
>       (if (< n 3) 1 (+ 1 (fib (- n 1)) (fib (- n 2))))))
>
>> (define fib2
>  (let ((+ +) (- -) (< <))
>   (lambda(n)
>     (if (< n 3) 1 (+ 1 (fib (- n 1)) (fib (- n 2)))))))
>
>> (time (fib  25) 1)
>(150049 (986 msec) (20776 bytes))
>
>> (time (fib2 25) 1)
>(150049 (916 msec) (3288 bytes))
>
>Here the code in the closure of fib2 uses only local variables
>and hence should be doing four fewer hash table lookups for
>each procedure call, but I don't see much in the way of time
>differences....
>
>I really expected a bigger time difference. The regular approach gets
>152K procedure calls per second (on a Powerbook G4 with jdk1.4)
>and the fancier approach gets 163K pc/sec which is about a 7% improvement.
>
>---Tim---

Re: [Jscheme-user] DynamicVariable proposal

[Toby A. <tob...@pe...>]

Your changes made things much better, but I still needed to make the
following changes to get serialisation to work correctly for me:

Index: src/jsint/DynamicVariable.java
===================================================================
RCS file: /cvsroot/jscheme/jscheme/src/jsint/DynamicVariable.java,v
retrieving revision 1.6
diff -u -r1.6 DynamicVariable.java
--- src/jsint/DynamicVariable.java	16 Jul 2004 22:02:13 -0000	1.6
+++ src/jsint/DynamicVariable.java	19 Jul 2004 23:27:15 -0000
@@ -59,10 +59,10 @@
 
     out.writeObject(name);
     try {
-      out.writeObject(getDynamicValue());
+      out.writeObject(value);
     } catch (java.io.IOException e) {
       System.out.println("Exception trying to serialize " +
-			 getDynamicValue() + ": " + e);
+			 value + ": " + e);
       throw e;
     }
   }
@@ -78,7 +78,7 @@
    **/
   private Object readResolve() throws java.io.ObjectStreamException {
     DynamicVariable it = Scheme.getInteractionEnvironment().intern(name);
-    if (it.value != U.UNDEFINED) it.value = value;
+    if (value != U.UNDEFINED) it.value = value;
     return it;
   }

The first change means that it won't barf when trying to serialise
Javadot values that refer to classes that aren't available in the
environment in which serialisation is taking place.

The second change just corrects a typo, I think.  Without it
deserialised DynamicVariables are always undefined.

Toby.

On Fri, Jul 16, 2004 at 06:10:09PM -0400, Ken Anderson wrote:
> I just made the changes for this.
> The Gabriel benchmarks show a 3% improvement.
> I should have tried your benchmark.
> 
> Toby,
> Can you test serialization and see if your patch is still needed.
> 
> k

Re: [Jscheme-user] DynamicVariable proposal

[Ken A. <kan...@bb...>]

I added your patches.
If you'd like to provide several unit tests for serialization, i'll add them to our test suit.

k