High performance (weak)dictionary implementation available?

Hi,

I'm having a performance problem with a Dictionary where the keys are
LargePositiveIntegers.

The following takes about 6 seconds on my machine (vw 7.4.1) and uses a
Dictionary:

Time millisecondsToRun: [
| d |
d := Dictionary new.
1 to: 10000 do: [:idx | d at: idx + SmallInteger maxVal put:
'something']]    

** Print-it: 6181

This on the other hand runs a lot faster (66 msec) and uses a
LensLinkedDictionary:

Time millisecondsToRun: [
| d |
d := LensLinkedDictionary new.
1 to: 10000 do: [:idx | d at: idx + SmallInteger maxVal put:
'something']]    

** Print-it: 66

Does anyone know what the drawback is of using the LensLinkedDictionary
over the Dictionary (after modifying it a bit so that it can work with
arbitrary keys)? Why isn't Dictionary made like it?

Actually I would like to have the performance of the
LensLinkedDictionary but in a WeakDictionary variant. Has anybody made
something like that (and is it publicly available?).

Thanks,
Mark

Mark,

I am happy to report that, on the development image / VM combination
that has all the hash changes we are currently evaluating, the
expression you mention takes so little time to evaluate that Time
millisecondsToRun: starts giving erratic results.  Adding 100
timesRepeat: to it causes evaluation to finish in 2879 milliseconds, for
roughly 29 milliseconds per iteration on average.

Thanks,
Andres.

-----Original Message-----
From: Mark Plas [mailto:[hidden email]]
Sent: Friday, November 02, 2007 9:35 AM
To: [hidden email]
Subject: High performance (weak)dictionary implementation available?

Hi,

I'm having a performance problem with a Dictionary where the keys are
LargePositiveIntegers.

The following takes about 6 seconds on my machine (vw 7.4.1) and uses a
Dictionary:

Time millisecondsToRun: [
| d |
d := Dictionary new.
1 to: 10000 do: [:idx | d at: idx + SmallInteger maxVal put:
'something']]    

** Print-it: 6181

This on the other hand runs a lot faster (66 msec) and uses a
LensLinkedDictionary:

Time millisecondsToRun: [
| d |
d := LensLinkedDictionary new.
1 to: 10000 do: [:idx | d at: idx + SmallInteger maxVal put:
'something']]    

** Print-it: 66

Does anyone know what the drawback is of using the LensLinkedDictionary
over the Dictionary (after modifying it a bit so that it can work with
arbitrary keys)? Why isn't Dictionary made like it?

Actually I would like to have the performance of the
LensLinkedDictionary but in a WeakDictionary variant. Has anybody made
something like that (and is it publicly available?).

Thanks,
Mark

Hi Andres,

Would these improvements become available with the 7.6 release? I guess
it will then require both a 7.6 VM and a 7.6 image? And what exactly are
these changes? Could you elaborate a bit on it?

As a side note, the reason why I ran into this was because I noticed
that in some experiment the time spent on inserting 10000 rows in an
Oracle database took about 20% database time and 80%
Dictionary>>findKeyOrNil:.

This made me think that it would be faster to have a Dictionary using an
Oracle database table for its storage rather than doing it in memory.

A small experiment shows that adding 10000 elements in the 'persistent
dictionary' (= insert into dictionary(key, value) values (..., ...))
takes about the same amount of time as the at:put: on Dictionary.
Retrieving the value of an element in the dictionary (= 'select value
from dictionary where key = ...') runs twice as fast as Dictionary>>at:
! All of this of course using LargePositiveIntegers as the key. This
came as a surprise to me.

It's good to hear that you've found a way to drastically improve this.

Mark

-----Original Message-----
From: Valloud, Andres [mailto:[hidden email]]
Sent: vrijdag 2 november 2007 17:50
To: Mark Plas; [hidden email]
Subject: RE: High performance (weak)dictionary implementation available?

Mark,

I am happy to report that, on the development image / VM combination
that has all the hash changes we are currently evaluating, the
expression you mention takes so little time to evaluate that Time
millisecondsToRun: starts giving erratic results.  Adding 100
timesRepeat: to it causes evaluation to finish in 2879 milliseconds, for
roughly 29 milliseconds per iteration on average.

Thanks,
Andres.

-----Original Message-----
From: Mark Plas [mailto:[hidden email]]
Sent: Friday, November 02, 2007 9:35 AM
To: [hidden email]
Subject: High performance (weak)dictionary implementation available?

Hi,

I'm having a performance problem with a Dictionary where the keys are
LargePositiveIntegers.

The following takes about 6 seconds on my machine (vw 7.4.1) and uses a
Dictionary:

Time millisecondsToRun: [
| d |
d := Dictionary new.
1 to: 10000 do: [:idx | d at: idx + SmallInteger maxVal put:
'something']]    

** Print-it: 6181

This on the other hand runs a lot faster (66 msec) and uses a
LensLinkedDictionary:

Time millisecondsToRun: [
| d |
d := LensLinkedDictionary new.
1 to: 10000 do: [:idx | d at: idx + SmallInteger maxVal put:
'something']]    

** Print-it: 66

Does anyone know what the drawback is of using the LensLinkedDictionary
over the Dictionary (after modifying it a bit so that it can work with
arbitrary keys)? Why isn't Dictionary made like it?

Actually I would like to have the performance of the
LensLinkedDictionary but in a WeakDictionary variant. Has anybody made
something like that (and is it publicly available?).

Thanks,
Mark

The fastest implementation I'm aware of is a tuned version of the cache
dictionaries in earlier versions of GemStone GBS--but not the GsToSt
implementation used following 6.2. Growth patterns are good. WeakArray
processing is good, performance is the best I've seen.

The implemenation is simply arrays of keys, values, and buckets. Use
empty key/value slots when available and put overflow in buckets.
Buckets are key and value arrays that are searched linearly--as opposed
to a linear search through the root. The hash range is critical, but
have no more than the number of buckets you can hash to. It is efficient
to have pre-grown buckets that front-end items and make use of knowing
the max slot used each bucket.

Most hashed collections are inefficient after containing more than the
maximum hash value number of items (16K for VW). The hash value returned
from LPI is unnecessarily computed and the computed value falls within a
narrow range. That means that hashing collections resort more frequently
to linear searches than is otherwise necessary. One of the biggest gains
you can make (since you are using LPI keys) is to implement LPI>>hash to
return "self".

At a more basic level, make sure you pre-size your collections to avoid
growth costs.

Paul Baumann
IntercontinentalExchange | ICE
2100 RiverEdge Pkwy | 5th Floor | Atlanta, GA 30328
Tel: 770.738.2137 | Fax: 770.951.1307 | Cel: 505.780.1470
[hidden email]

24-hour ice helpdesk 770.738.2101
www.theice.com

-----Original Message-----
From: Mark Plas [mailto:[hidden email]]
Sent: Friday, November 02, 2007 12:35 PM
To: [hidden email]
Subject: High performance (weak)dictionary implementation available?

Hi,

I'm having a performance problem with a Dictionary where the keys are
LargePositiveIntegers.

The following takes about 6 seconds on my machine (vw 7.4.1) and uses a
Dictionary:

Time millisecondsToRun: [
| d |
d := Dictionary new.
1 to: 10000 do: [:idx | d at: idx + SmallInteger maxVal put:
'something']]    

** Print-it: 6181

This on the other hand runs a lot faster (66 msec) and uses a
LensLinkedDictionary:

Time millisecondsToRun: [
| d |
d := LensLinkedDictionary new.
1 to: 10000 do: [:idx | d at: idx + SmallInteger maxVal put:
'something']]    

** Print-it: 66

Does anyone know what the drawback is of using the LensLinkedDictionary
over the Dictionary (after modifying it a bit so that it can work with
arbitrary keys)? Why isn't Dictionary made like it?

Actually I would like to have the performance of the
LensLinkedDictionary but in a WeakDictionary variant. Has anybody made
something like that (and is it publicly available?).

Thanks,
Mark
 
--------------------------------------------------------
This message may contain confidential information and is intended for specific recipients unless explicitly noted otherwise. If you have reason to believe you are not an intended recipient of this message, please delete it and notify the sender. This message may not represent the opinion of IntercontinentalExchange, Inc. (ICE), its subsidiaries or affiliates, and does not constitute a contract or guarantee. Unencrypted electronic mail is not secure and the recipient of this message is expected to provide safeguards from viruses and pursue alternate means of communication where privacy or a binding message is desired.

Mark,

We are still in the process of reviewing the changes, and this has not
been finalized yet.  I think the best way to describe them would be via
the release notes.  I will let you know when they become available.

Thanks,
Andres.

Mark Plas wrote:

Paul,

I've been working on this with GemStone.  The interesting primitive
indexOf:replaceWith:startingAt:stoppingAt: is now 15% faster for small
cases and 35% faster for large cases as a result of this collaboration.

Thanks,
Andres.

Paul Baumann wrote:

Andres,

Yes, initial tests show that use of
#indexOf:replaceWith:startingAt:stoppingAt: does reduce bucket iteration
costs, and only three methods needed to be changed to use it. Thanks. I
love those kinds of changes.

Paul Baumann
[hidden email]

-----Original Message-----
From: Andres Valloud [mailto:[hidden email]]
Sent: Monday, November 05, 2007 2:04 PM
To: [hidden email]
Subject: Re: High performance (weak)dictionary implementation available?

Paul,

I've been working on this with GemStone.  The interesting primitive
indexOf:replaceWith:startingAt:stoppingAt: is now 15% faster for small
cases and 35% faster for large cases as a result of this collaboration.

Thanks,
Andres.

Paul Baumann wrote:
> It is efficient to have pre-grown buckets that front-end items and
> make use of knowing the max slot used each bucket.
>
> Most hashed collections are inefficient after containing more than the

> maximum hash value number of items (16K for VW). The hash value
> returned from LPI is unnecessarily computed and the computed value
> falls within a narrow range. That means that hashing collections
> resort more frequently to linear searches than is otherwise necessary.
it?
>
> Actually I would like to have the performance of the
> LensLinkedDictionary but in a WeakDictionary variant. Has anybody made

> something like that (and is it publicly available?).
>
> Thanks,
> Mark
>  
> --------------------------------------------------------
> This message may contain confidential information and is intended for
specific recipients unless explicitly noted otherwise. If you have
reason to believe you are not an intended recipient of this message,
please delete it and notify the sender. This message may not represent
the opinion of IntercontinentalExchange, Inc. (ICE), its subsidiaries or
affiliates, and does not constitute a contract or guarantee. Unencrypted
electronic mail is not secure and the recipient of this message is
expected to provide safeguards from viruses and pursue alternate means
of communication where privacy or a binding message is desired.
>
>
>
 
--------------------------------------------------------
This message may contain confidential information and is intended for specific recipients unless explicitly noted otherwise. If you have reason to believe you are not an intended recipient of this message, please delete it and notify the sender. This message may not represent the opinion of IntercontinentalExchange, Inc. (ICE), its subsidiaries or affiliates, and does not constitute a contract or guarantee. Unencrypted electronic mail is not secure and the recipient of this message is expected to provide safeguards from viruses and pursue alternate means of communication where privacy or a binding message is desired.

Paul,

Thank you for your kind comments.  Please let us know if you need
anything else.

Thanks,
Andres.

-----Original Message-----
From: Paul Baumann [mailto:[hidden email]]
Sent: Tuesday, November 06, 2007 12:40 PM
To: Andres Valloud; [hidden email]
Subject: RE: High performance (weak)dictionary implementation available?

Andres,

Yes, initial tests show that use of
#indexOf:replaceWith:startingAt:stoppingAt: does reduce bucket iteration
costs, and only three methods needed to be changed to use it. Thanks. I
love those kinds of changes.

Paul Baumann
[hidden email]

-----Original Message-----
From: Andres Valloud [mailto:[hidden email]]
Sent: Monday, November 05, 2007 2:04 PM
To: [hidden email]
Subject: Re: High performance (weak)dictionary implementation available?

Paul,

I've been working on this with GemStone.  The interesting primitive
indexOf:replaceWith:startingAt:stoppingAt: is now 15% faster for small
cases and 35% faster for large cases as a result of this collaboration.

Thanks,
Andres.

Paul Baumann wrote:
> It is efficient to have pre-grown buckets that front-end items and
> make use of knowing the max slot used each bucket.
>
> Most hashed collections are inefficient after containing more than the

> maximum hash value number of items (16K for VW). The hash value
> returned from LPI is unnecessarily computed and the computed value
> falls within a narrow range. That means that hashing collections
> resort more frequently to linear searches than is otherwise necessary.
it?
>
> Actually I would like to have the performance of the
> LensLinkedDictionary but in a WeakDictionary variant. Has anybody made

> something like that (and is it publicly available?).
>
> Thanks,
> Mark
>  
> --------------------------------------------------------
> This message may contain confidential information and is intended for
specific recipients unless explicitly noted otherwise. If you have
reason to believe you are not an intended recipient of this message,
please delete it and notify the sender. This message may not represent
the opinion of IntercontinentalExchange, Inc. (ICE), its subsidiaries or
affiliates, and does not constitute a contract or guarantee. Unencrypted
electronic mail is not secure and the recipient of this message is
expected to provide safeguards from viruses and pursue alternate means
of communication where privacy or a binding message is desired.
>
>
>
 
--------------------------------------------------------
This message may contain confidential information and is intended for
specific recipients unless explicitly noted otherwise. If you have
reason to believe you are not an intended recipient of this message,
please delete it and notify the sender. This message may not represent
the opinion of IntercontinentalExchange, Inc. (ICE), its subsidiaries or
affiliates, and does not constitute a contract or guarantee. Unencrypted
electronic mail is not secure and the recipient of this message is
expected to provide safeguards from viruses and pursue alternate means
of communication where privacy or a binding message is desired.

Hi Paul,

Thanks for the detailed information. I've done some searching and found
OtWeakValueDictionary that comes with OpenTalk. Compared to other
dictionary implementations, this one is a lot faster when it comes down
to adding for instance 30000 elements (more than 16K) to a dictionary
(with SmallInteger keys).

With LPI keys it is slow, so I've copied the class and changed it a
littlebit so that it doesn't use #hash to get the hash value but another
method which I implemented on LPI as ^self (I didn't want to change the
default hash behavior on LPI. I don't know what the effects might be).

This seems to work very well and is probably good enough for the things
I'm doing.

Mark

-----Original Message-----
From: Paul Baumann [mailto:[hidden email]]
Sent: maandag 5 november 2007 16:23
To: Mark Plas; [hidden email]
Subject: RE: High performance (weak)dictionary implementation available?

The fastest implementation I'm aware of is a tuned version of the cache
dictionaries in earlier versions of GemStone GBS--but not the GsToSt
implementation used following 6.2. Growth patterns are good. WeakArray
processing is good, performance is the best I've seen.

The implemenation is simply arrays of keys, values, and buckets. Use
empty key/value slots when available and put overflow in buckets.
Buckets are key and value arrays that are searched linearly--as opposed
to a linear search through the root. The hash range is critical, but
have no more than the number of buckets you can hash to. It is efficient
to have pre-grown buckets that front-end items and make use of knowing
the max slot used each bucket.

Most hashed collections are inefficient after containing more than the
maximum hash value number of items (16K for VW). The hash value returned
from LPI is unnecessarily computed and the computed value falls within a
narrow range. That means that hashing collections resort more frequently
to linear searches than is otherwise necessary. One of the biggest gains
you can make (since you are using LPI keys) is to implement LPI>>hash to
return "self".

At a more basic level, make sure you pre-size your collections to avoid
growth costs.

Paul Baumann
IntercontinentalExchange | ICE
2100 RiverEdge Pkwy | 5th Floor | Atlanta, GA 30328
Tel: 770.738.2137 | Fax: 770.951.1307 | Cel: 505.780.1470
[hidden email]

24-hour ice helpdesk 770.738.2101
www.theice.com

-----Original Message-----
From: Mark Plas [mailto:[hidden email]]
Sent: Friday, November 02, 2007 12:35 PM
To: [hidden email]
Subject: High performance (weak)dictionary implementation available?

Hi,

I'm having a performance problem with a Dictionary where the keys are
LargePositiveIntegers.

The following takes about 6 seconds on my machine (vw 7.4.1) and uses a
Dictionary:

Time millisecondsToRun: [
| d |
d := Dictionary new.
1 to: 10000 do: [:idx | d at: idx + SmallInteger maxVal put:
'something']]    

** Print-it: 6181

This on the other hand runs a lot faster (66 msec) and uses a
LensLinkedDictionary:

Time millisecondsToRun: [
| d |
d := LensLinkedDictionary new.
1 to: 10000 do: [:idx | d at: idx + SmallInteger maxVal put:
'something']]    

** Print-it: 66

Does anyone know what the drawback is of using the LensLinkedDictionary
over the Dictionary (after modifying it a bit so that it can work with
arbitrary keys)? Why isn't Dictionary made like it?

Actually I would like to have the performance of the
LensLinkedDictionary but in a WeakDictionary variant. Has anybody made
something like that (and is it publicly available?).

Thanks,
Mark
 
--------------------------------------------------------
This message may contain confidential information and is intended for
specific recipients unless explicitly noted otherwise. If you have
reason to believe you are not an intended recipient of this message,
please delete it and notify the sender. This message may not represent
the opinion of IntercontinentalExchange, Inc. (ICE), its subsidiaries or
affiliates, and does not constitute a contract or guarantee. Unencrypted
electronic mail is not secure and the recipient of this message is
expected to provide safeguards from viruses and pursue alternate means
of communication where privacy or a binding message is desired.

BTW,

Using a method other than #hash is good. One way that can be leveraged
is to bit-join the class hash with the instance hash to get greater
range. That trick only works if you have control of class changes. GBS
changes classes for example so GBS class change code needs to know to
re-cache on class changes.

Changing LPI>>hash has had no negative effects that we've observed. I
recall searching VW images for potential resolution problems that could
follow a change like that. No LPI's were in hashed collections. Cincom
had looked into making the change but the effort to ensure LPI's will
resolve afterwards was probably a little too much. YMMV, but the change
works fine for us.

In terms of GBS tuning, even greater performance can be achieved by
avoiding nearly a third the cache activity (StToGs)--by declaring an
abstract class that is delegate-aware and that domain classes can be
subclassed from. Instances of kernel classes still get cached. A few GBS
methods need to be changed to use the new delegate resolution.

Even greater GBS performance improvements can be found by entirely
avoiding the caching of delegates where GS identity doesn't need to be
preserved. This is why people used the now deprecated
#asLocalObjectCopy, but really what users need is a way to selectively
control what is a replicate and what is a copy. A #copy declaration in
replication specs is an obvious step in that direction, but class-based
rules are good too.

I'll look into OtWeakValueDictionary. The tuned dictionaries I work with
have excellent and consistent performance for all types of access and
are tested to 2M objects. With the tuning that Andre mentioned, that
will put performance to new levels because it greatly reduces the most
significant cost that remained of that design.

Paul Baumann

-----Original Message-----
From: Mark Plas [mailto:[hidden email]]
Sent: Wednesday, November 07, 2007 8:55 AM
To: Paul Baumann; [hidden email]
Subject: RE: High performance (weak)dictionary implementation available?
Importance: High

Hi Paul,

Thanks for the detailed information. I've done some searching and found
OtWeakValueDictionary that comes with OpenTalk. Compared to other
dictionary implementations, this one is a lot faster when it comes down
to adding for instance 30000 elements (more than 16K) to a dictionary
(with SmallInteger keys).

With LPI keys it is slow, so I've copied the class and changed it a
littlebit so that it doesn't use #hash to get the hash value but another
method which I implemented on LPI as ^self (I didn't want to change the
default hash behavior on LPI. I don't know what the effects might be).

This seems to work very well and is probably good enough for the things
I'm doing.

Mark

-----Original Message-----
From: Paul Baumann [mailto:[hidden email]]
Sent: maandag 5 november 2007 16:23
To: Mark Plas; [hidden email]
Subject: RE: High performance (weak)dictionary implementation available?

The fastest implementation I'm aware of is a tuned version of the cache
dictionaries in earlier versions of GemStone GBS--but not the GsToSt
implementation used following 6.2. Growth patterns are good. WeakArray
processing is good, performance is the best I've seen.

The implemenation is simply arrays of keys, values, and buckets. Use
empty key/value slots when available and put overflow in buckets.
Buckets are key and value arrays that are searched linearly--as opposed
to a linear search through the root. The hash range is critical, but
have no more than the number of buckets you can hash to. It is efficient
to have pre-grown buckets that front-end items and make use of knowing
the max slot used each bucket.

Most hashed collections are inefficient after containing more than the
maximum hash value number of items (16K for VW). The hash value returned
from LPI is unnecessarily computed and the computed value falls within a
narrow range. That means that hashing collections resort more frequently
to linear searches than is otherwise necessary. One of the biggest gains
you can make (since you are using LPI keys) is to implement LPI>>hash to
return "self".

At a more basic level, make sure you pre-size your collections to avoid
growth costs.

Paul Baumann
IntercontinentalExchange | ICE
2100 RiverEdge Pkwy | 5th Floor | Atlanta, GA 30328
Tel: 770.738.2137 | Fax: 770.951.1307 | Cel: 505.780.1470
[hidden email]

24-hour ice helpdesk 770.738.2101
www.theice.com

-----Original Message-----
From: Mark Plas [mailto:[hidden email]]
Sent: Friday, November 02, 2007 12:35 PM
To: [hidden email]
Subject: High performance (weak)dictionary implementation available?

Hi,

I'm having a performance problem with a Dictionary where the keys are
LargePositiveIntegers.

The following takes about 6 seconds on my machine (vw 7.4.1) and uses a
Dictionary:

Time millisecondsToRun: [
| d |
d := Dictionary new.
1 to: 10000 do: [:idx | d at: idx + SmallInteger maxVal put:
'something']]    

** Print-it: 6181

This on the other hand runs a lot faster (66 msec) and uses a
LensLinkedDictionary:

Time millisecondsToRun: [
| d |
d := LensLinkedDictionary new.
1 to: 10000 do: [:idx | d at: idx + SmallInteger maxVal put:
'something']]    

** Print-it: 66

Does anyone know what the drawback is of using the LensLinkedDictionary
over the Dictionary (after modifying it a bit so that it can work with
arbitrary keys)? Why isn't Dictionary made like it?

Actually I would like to have the performance of the
LensLinkedDictionary but in a WeakDictionary variant. Has anybody made
something like that (and is it publicly available?).

Thanks,
Mark
 
--------------------------------------------------------
This message may contain confidential information and is intended for
specific recipients unless explicitly noted otherwise. If you have
reason to believe you are not an intended recipient of this message,
please delete it and notify the sender. This message may not represent
the opinion of IntercontinentalExchange, Inc. (ICE), its subsidiaries or
affiliates, and does not constitute a contract or guarantee. Unencrypted
electronic mail is not secure and the recipient of this message is
expected to provide safeguards from viruses and pursue alternate means
of communication where privacy or a binding message is desired.
 
--------------------------------------------------------
This message may contain confidential information and is intended for specific recipients unless explicitly noted otherwise. If you have reason to believe you are not an intended recipient of this message, please delete it and notify the sender. This message may not represent the opinion of IntercontinentalExchange, Inc. (ICE), its subsidiaries or affiliates, and does not constitute a contract or guarantee. Unencrypted electronic mail is not secure and the recipient of this message is expected to provide safeguards from viruses and pursue alternate means of communication where privacy or a binding message is desired.

Hi Paul,

  "I'll look into OtWeakValueDictionary. The tuned dictionaries I work
with
  have excellent and consistent performance for all types of access and
  are tested to 2M objects. With the tuning that Andre mentioned, that
  will put performance to new levels because it greatly reduces the most
  significant cost that remained of that design."

Just to see what would happen, I tried to put 1 million objects in my
'tweaked' OtWeakValueDictionary.

|d|
d := WeakValueDictionary new.
Time millisecondsToRun: [
        1 to: 1000000 do: [:i | d at: i + SmallInteger maxVal  put:
'test' ]
  ]

With SmallInteger keys it takes about 1.1 seconds. with LPI (like in the
example) it takes 6.2secs. This sounds good to me. Memory wise however,
after performing a GC, the message "heap shrunk by 52.17 Mbytes"
appeared.

Do the Gemstone dictionaries perform better?

[as a side note: I also found two easy to fix bugs in the
OtWeakValueDictionary: #includesKey: doesn't work and #size isn't
implemented on it]

Mark

Mark et al,

Note that when you test with a WeakValueDictionary, running it to
100,000 will consume about 95% of its execution time reclaiming objects
that were garbage collected.  If we replace the weak dictionary with a
plain Dictionary so we can compare just the difference in hashing
performance, running the loop with 1,000,000 runs in about 3.7 seconds
here.  The small integer case number I get is the same as yours.

Thanks,
Andres.

-----Original Message-----
From: Mark Plas [mailto:[hidden email]]
Sent: Wednesday, November 07, 2007 7:49 AM
To: Paul Baumann; [hidden email]
Subject: RE: High performance (weak)dictionary implementation available?

Hi Paul,

  "I'll look into OtWeakValueDictionary. The tuned dictionaries I work
with
  have excellent and consistent performance for all types of access and
  are tested to 2M objects. With the tuning that Andre mentioned, that
  will put performance to new levels because it greatly reduces the most
  significant cost that remained of that design."

Just to see what would happen, I tried to put 1 million objects in my
'tweaked' OtWeakValueDictionary.

|d|
d := WeakValueDictionary new.
Time millisecondsToRun: [
        1 to: 1000000 do: [:i | d at: i + SmallInteger maxVal  put:
'test' ]
  ]

With SmallInteger keys it takes about 1.1 seconds. with LPI (like in the
example) it takes 6.2secs. This sounds good to me. Memory wise however,
after performing a GC, the message "heap shrunk by 52.17 Mbytes"
appeared.

Do the Gemstone dictionaries perform better?

[as a side note: I also found two easy to fix bugs in the
OtWeakValueDictionary: #includesKey: doesn't work and #size isn't
implemented on it]

Mark

Hi Andres,

My example has a somewhat hidden feature in it. Its values can't get
garbage collected because its always the same string 'test' I'm adding
which is held onto strongly be the CompiledMethod needed for the doit.

I changed it to put the value in a temp var and the performance stays
the same (as would be expected).

When I send 'copy' to the value it suddenly runs faster in 2.6 seconds
which is explained by the garbage collecting going on.

Could the 3.7 seconds that you get be explained by not having a critical
section round the #at: and #at:put: methods in an ordinary dictionary?

Anyhow, having your improvements available for every dictionary is
something to look forward to.

Mark

-----Original Message-----
From: Valloud, Andres [mailto:[hidden email]]
Sent: woensdag 7 november 2007 17:01
To: Mark Plas; Paul Baumann; [hidden email]
Subject: RE: High performance (weak)dictionary implementation available?

Mark et al,

Note that when you test with a WeakValueDictionary, running it to
100,000 will consume about 95% of its execution time reclaiming objects
that were garbage collected.  If we replace the weak dictionary with a
plain Dictionary so we can compare just the difference in hashing
performance, running the loop with 1,000,000 runs in about 3.7 seconds
here.  The small integer case number I get is the same as yours.

Thanks,
Andres.

-----Original Message-----
From: Mark Plas [mailto:[hidden email]]
Sent: Wednesday, November 07, 2007 7:49 AM
To: Paul Baumann; [hidden email]
Subject: RE: High performance (weak)dictionary implementation available?

Hi Paul,

  "I'll look into OtWeakValueDictionary. The tuned dictionaries I work
with
  have excellent and consistent performance for all types of access and
  are tested to 2M objects. With the tuning that Andre mentioned, that
  will put performance to new levels because it greatly reduces the most
  significant cost that remained of that design."

Just to see what would happen, I tried to put 1 million objects in my
'tweaked' OtWeakValueDictionary.

|d|
d := WeakValueDictionary new.
Time millisecondsToRun: [
        1 to: 1000000 do: [:i | d at: i + SmallInteger maxVal  put:
'test' ]
  ]

With SmallInteger keys it takes about 1.1 seconds. with LPI (like in the
example) it takes 6.2secs. This sounds good to me. Memory wise however,
after performing a GC, the message "heap shrunk by 52.17 Mbytes"
appeared.

Do the Gemstone dictionaries perform better?

[as a side note: I also found two easy to fix bugs in the
OtWeakValueDictionary: #includesKey: doesn't work and #size isn't
implemented on it]

Mark

Here are the metrics you asked for:

| items d |
d := WeakValueDictionary new.
items := (1 to: 1000000) collect: [:i | i + Core.SmallInteger maxVal ].
Core.Time microsecondsToRun: [
        items do: [:i | d at: i  put: 'test' ]
].
 3687824
 3065236
 2873137

| items d |
d := WeakValueDictionary new: 1000000.
items := (1 to: 1000000) collect: [:i | i + Core.SmallInteger maxVal ].
Core.Time microsecondsToRun: [
        items do: [:i | d at: i  put: 'test' ]
].
 2952143
 2717090
 3276513


| items d |
d := IcxIntegerKeyValueDictionary newWeakValues: 1000000.
items := (1 to: 1000000) collect: [:i | i + Core.SmallInteger maxVal ].
Core.Time microsecondsToRun: [
        items do: [:i | d at: i  put: 'test' ]
].
 1259675
 1268125
 1231661

IcxIntegerKeyValueDictionary is an ICE defined subclass of the GBS
GbxLargeDictionary that is highly tuned. These numbers are prior to the
improvements that Andres mentioned.

Paul Baumann

-----Original Message-----
From: Mark Plas [mailto:[hidden email]]
Sent: Wednesday, November 07, 2007 11:16 AM
To: Valloud, Andres; Paul Baumann; [hidden email]
Subject: RE: High performance (weak)dictionary implementation available?
Importance: High

Hi Andres,

My example has a somewhat hidden feature in it. Its values can't get
garbage collected because its always the same string 'test' I'm adding
which is held onto strongly be the CompiledMethod needed for the doit.

I changed it to put the value in a temp var and the performance stays
the same (as would be expected).

When I send 'copy' to the value it suddenly runs faster in 2.6 seconds
which is explained by the garbage collecting going on.

Could the 3.7 seconds that you get be explained by not having a critical
section round the #at: and #at:put: methods in an ordinary dictionary?

Anyhow, having your improvements available for every dictionary is
something to look forward to.

Mark

-----Original Message-----
From: Valloud, Andres [mailto:[hidden email]]
Sent: woensdag 7 november 2007 17:01
To: Mark Plas; Paul Baumann; [hidden email]
Subject: RE: High performance (weak)dictionary implementation available?

Mark et al,

Note that when you test with a WeakValueDictionary, running it to
100,000 will consume about 95% of its execution time reclaiming objects
that were garbage collected.  If we replace the weak dictionary with a
plain Dictionary so we can compare just the difference in hashing
performance, running the loop with 1,000,000 runs in about 3.7 seconds
here.  The small integer case number I get is the same as yours.

Thanks,
Andres.

-----Original Message-----
From: Mark Plas [mailto:[hidden email]]
Sent: Wednesday, November 07, 2007 7:49 AM
To: Paul Baumann; [hidden email]
Subject: RE: High performance (weak)dictionary implementation available?

Hi Paul,

  "I'll look into OtWeakValueDictionary. The tuned dictionaries I work
with
  have excellent and consistent performance for all types of access and
  are tested to 2M objects. With the tuning that Andre mentioned, that
  will put performance to new levels because it greatly reduces the most
  significant cost that remained of that design."

Just to see what would happen, I tried to put 1 million objects in my
'tweaked' OtWeakValueDictionary.

|d|
d := WeakValueDictionary new.
Time millisecondsToRun: [
        1 to: 1000000 do: [:i | d at: i + SmallInteger maxVal  put:
'test' ]
  ]

With SmallInteger keys it takes about 1.1 seconds. with LPI (like in the
example) it takes 6.2secs. This sounds good to me. Memory wise however,
after performing a GC, the message "heap shrunk by 52.17 Mbytes"
appeared.

Do the Gemstone dictionaries perform better?

[as a side note: I also found two easy to fix bugs in the
OtWeakValueDictionary: #includesKey: doesn't work and #size isn't
implemented on it]

Mark
 
--------------------------------------------------------
This message may contain confidential information and is intended for specific recipients unless explicitly noted otherwise. If you have reason to believe you are not an intended recipient of this message, please delete it and notify the sender. This message may not represent the opinion of IntercontinentalExchange, Inc. (ICE), its subsidiaries or affiliates, and does not constitute a contract or guarantee. Unencrypted electronic mail is not secure and the recipient of this message is expected to provide safeguards from viruses and pursue alternate means of communication where privacy or a binding message is desired.

Ah, I found a small problem in WeakKeyDictionary>>grow.  Now I get the
same time you get.  However, a time profiler reveals that the run time
is dominated by the dictionary growing.  I will take a better look at
this later.

Thanks,
Andres.

-----Original Message-----
From: Mark Plas [mailto:[hidden email]]
Sent: Wednesday, November 07, 2007 8:16 AM
To: Valloud, Andres; Paul Baumann; [hidden email]
Subject: RE: High performance (weak)dictionary implementation available?

Hi Andres,

My example has a somewhat hidden feature in it. Its values can't get
garbage collected because its always the same string 'test' I'm adding
which is held onto strongly be the CompiledMethod needed for the doit.

I changed it to put the value in a temp var and the performance stays
the same (as would be expected).

When I send 'copy' to the value it suddenly runs faster in 2.6 seconds
which is explained by the garbage collecting going on.

Could the 3.7 seconds that you get be explained by not having a critical
section round the #at: and #at:put: methods in an ordinary dictionary?

Anyhow, having your improvements available for every dictionary is
something to look forward to.

Mark

-----Original Message-----
From: Valloud, Andres [mailto:[hidden email]]
Sent: woensdag 7 november 2007 17:01
To: Mark Plas; Paul Baumann; [hidden email]
Subject: RE: High performance (weak)dictionary implementation available?

Mark et al,

Note that when you test with a WeakValueDictionary, running it to
100,000 will consume about 95% of its execution time reclaiming objects
that were garbage collected.  If we replace the weak dictionary with a
plain Dictionary so we can compare just the difference in hashing
performance, running the loop with 1,000,000 runs in about 3.7 seconds
here.  The small integer case number I get is the same as yours.

Thanks,
Andres.

-----Original Message-----
From: Mark Plas [mailto:[hidden email]]
Sent: Wednesday, November 07, 2007 7:49 AM
To: Paul Baumann; [hidden email]
Subject: RE: High performance (weak)dictionary implementation available?

Hi Paul,

  "I'll look into OtWeakValueDictionary. The tuned dictionaries I work
with
  have excellent and consistent performance for all types of access and
  are tested to 2M objects. With the tuning that Andre mentioned, that
  will put performance to new levels because it greatly reduces the most
  significant cost that remained of that design."

Just to see what would happen, I tried to put 1 million objects in my
'tweaked' OtWeakValueDictionary.

|d|
d := WeakValueDictionary new.
Time millisecondsToRun: [
        1 to: 1000000 do: [:i | d at: i + SmallInteger maxVal  put:
'test' ]
  ]

With SmallInteger keys it takes about 1.1 seconds. with LPI (like in the
example) it takes 6.2secs. This sounds good to me. Memory wise however,
after performing a GC, the message "heap shrunk by 52.17 Mbytes"
appeared.

Do the Gemstone dictionaries perform better?

[as a side note: I also found two easy to fix bugs in the
OtWeakValueDictionary: #includesKey: doesn't work and #size isn't
implemented on it]

Mark

Mark Plas wrote:
Making a really fast general-purpose collection isn't easy, since "fast"
and "general-purpose" tend to drive designs in different directions. If
you need a fast collection, it's sometimes easier to just make an
application-specific one.

For instance, in recent versions of GBS, we don't use a dictionary with
integer keys, we use an application-specific key, a delegate. The
delegate contains the moral equivalent of a large integer, in the form
of eight bytes, and some other information in other bytes. To avoid
creating instances of large integer, we never use more than three bytes
of the 8-byte number at a time, and we also use the knowledge that three
of those bytes have predictable values so we can focus on the other five
bytes. The structure is a shallow fixed-depth tree, keyed by the upper
two bytes. Each extant leaf is a hashed collection using collision
chains, keyed by a SmallInteger made from the remaining three bytes.
It's fairly new, and we may be able to make it faster over time, but it
performs pretty well now. Here's the equivalent performance test for it
(pre-grown, keys pre-allocated, measuring only the time to do the
key/value inserts):

| sess items d |
sess := GBSM currentSession.
sess configuration initialCacheSize: 1000000.
d := GbxObjIdDictionary newForSession: sess.
d at: (GbxDelegate oopValue: Core.SmallInteger maxVal + 2 session: sess)
        put: 'initialization'. "This pre-grows the leaf we're going to use."
items := (1 to: 1000000) collect:
                                [:i |
                                GbxDelegate oopValue: Core.SmallInteger maxVal + 2 + (256 * i)
"Low-order byte must be 16r01, is ignored in lookups"
                                        session: sess].
Core.Time microsecondsToRun: [items do: [:i | d at: i put: 'test']]
  270908
  262620
  272041


My machine is probably not the same speed as yours, so for comparison
(both of the following tests were run with LPI hash answering self):

| items d |
d := IcxIntegerKeyValueDictionary newWeakValues: 1000000.
items := (1 to: 1000000) collect: [:i | i + Core.SmallInteger maxVal ].
Core.Time microsecondsToRun: [
        items do: [:i | d at: i  put: 'test' ]
].
  693125
  673641
  687493

(Note that I don't have Paul's latest version of
IcxIntegerKeyValueDictionary, so this may be slower than a current version)


| items d |
d := OtWeakValueDictionary new: 1000000.
items := (1 to: 1000000) collect: [:i | i + Core.SmallInteger maxVal].
Core.Time microsecondsToRun: [items do: [:i | d at: i put: 'test']]
  3088544
  1919450
  3085262

Regards,

-Martin

Hi Martin, Paul,

Those are impressive measurements. The improvements over the OpenTalk
dictionary are in a range of 2.8x - 11.4x! It also shows very clearly
the advantages you can have when knowing something about the way your
keys are structured.

Thanks for the information,
Mark

-----Original Message-----
From: Martin McClure [mailto:[hidden email]]
Sent: donderdag 8 november 2007 3:46
To: Mark Plas
Cc: Paul Baumann; [hidden email]
Subject: Re: High performance (weak)dictionary implementation available?

Mark Plas wrote:
> Hi Paul,
>
>   "I'll look into OtWeakValueDictionary. The tuned dictionaries I work
> with
>   have excellent and consistent performance for all types of access
and
>   are tested to 2M objects. With the tuning that Andre mentioned, that
>   will put performance to new levels because it greatly reduces the
most the
> example) it takes 6.2secs. This sounds good to me. Memory wise
however,
> after performing a GC, the message "heap shrunk by 52.17 Mbytes"
> appeared.
>
> Do the Gemstone dictionaries perform better?

Making a really fast general-purpose collection isn't easy, since "fast"

and "general-purpose" tend to drive designs in different directions. If
you need a fast collection, it's sometimes easier to just make an
application-specific one.

For instance, in recent versions of GBS, we don't use a dictionary with
integer keys, we use an application-specific key, a delegate. The
delegate contains the moral equivalent of a large integer, in the form
of eight bytes, and some other information in other bytes. To avoid
creating instances of large integer, we never use more than three bytes
of the 8-byte number at a time, and we also use the knowledge that three

of those bytes have predictable values so we can focus on the other five

bytes. The structure is a shallow fixed-depth tree, keyed by the upper
two bytes. Each extant leaf is a hashed collection using collision
chains, keyed by a SmallInteger made from the remaining three bytes.
It's fairly new, and we may be able to make it faster over time, but it
performs pretty well now. Here's the equivalent performance test for it
(pre-grown, keys pre-allocated, measuring only the time to do the
key/value inserts):

| sess items d |
sess := GBSM currentSession.
sess configuration initialCacheSize: 1000000.
d := GbxObjIdDictionary newForSession: sess.
d at: (GbxDelegate oopValue: Core.SmallInteger maxVal + 2 session: sess)
        put: 'initialization'. "This pre-grows the leaf we're going to
use."
items := (1 to: 1000000) collect:
                                [:i |
                                GbxDelegate oopValue: Core.SmallInteger
maxVal + 2 + (256 * i)
"Low-order byte must be 16r01, is ignored in lookups"
                                        session: sess].
Core.Time microsecondsToRun: [items do: [:i | d at: i put: 'test']]
  270908
  262620
  272041


My machine is probably not the same speed as yours, so for comparison
(both of the following tests were run with LPI hash answering self):

| items d |
d := IcxIntegerKeyValueDictionary newWeakValues: 1000000.
items := (1 to: 1000000) collect: [:i | i + Core.SmallInteger maxVal ].
Core.Time microsecondsToRun: [
        items do: [:i | d at: i  put: 'test' ]
].
  693125
  673641
  687493

(Note that I don't have Paul's latest version of
IcxIntegerKeyValueDictionary, so this may be slower than a current
version)


| items d |
d := OtWeakValueDictionary new: 1000000.
items := (1 to: 1000000) collect: [:i | i + Core.SmallInteger maxVal].
Core.Time microsecondsToRun: [items do: [:i | d at: i put: 'test']]
  3088544
  1919450
  3085262

Regards,

-Martin