Re: [Pharo-project] Migrated HashTable from ss to SmalltalkHub
Interesting, nice thesis Camilo. Why not replace Dictionary then? At least it should be integrated into Collections, in the image. Fernando On Sun, Feb 10, 2013 at 4:38 PM, Camillo Bruni <camillobruni@gmail.com>wrote:
On 2013-02-10, at 16:34, stephane ducasse <stephane.ducasse@free.fr> wrote:
On Feb 10, 2013, at 4:22 PM, Sven Van Caekenberghe <sven@stfx.eu> wrote:
On 10 Feb 2013, at 15:16, Stéphane Ducasse <stephane.ducasse@inria.fr>
wrote:
- migrated all the history - defined configurationOf - All tests are green under 1.4 and 2.0
Stef
Dear I ask: what is HastTable and how it is different from Dictionary ?
I think it's a dictionary implementation based on buckets (as any other decent dictionary implementation does...)
I've shown in my master thesis that a simple bucket-based dictionary can outperform our poor-mans single array collection dictionary in almost every operation. The only drawback is the slightly bigger size in memory.
On 2013-02-10, at 17:07, Fernando Olivero <fernando.olivero@usi.ch> wrote:
Interesting, nice thesis Camilo. Why not replace Dictionary then? At least it should be integrated into Collections, in the image. Fernando
at some point we might do it ;), we proposed this 3 years ago, but I guess Pharo wasn't ready back then... Currently I prefer replacing all the shitty streaming stuff with XTreams in 3.0.
On 10 Feb 2013, at 17:07, Fernando Olivero <fernando.olivero@usi.ch> wrote:
Interesting, nice thesis Camilo. Why not replace Dictionary then? At least it should be integrated into Collections, in the image. Fernando
Yes, cool stuff, nice thesis; more stuff to read⦠If you did all this work, and it is provably better, then indeed, it should at least be an alternative in the collection framework. BTW, regarding space, a dictionary that starts as a SmallDictionary internally and adjust itself according to usage would be ideal, the there is no price to pay.
On Sun, Feb 10, 2013 at 4:38 PM, Camillo Bruni <camillobruni@gmail.com> wrote:
On 2013-02-10, at 16:34, stephane ducasse <stephane.ducasse@free.fr> wrote:
On Feb 10, 2013, at 4:22 PM, Sven Van Caekenberghe <sven@stfx.eu> wrote:
On 10 Feb 2013, at 15:16, Stéphane Ducasse <stephane.ducasse@inria.fr> wrote:
- migrated all the history - defined configurationOf - All tests are green under 1.4 and 2.0
Stef
Dear I ask: what is HastTable and how it is different from Dictionary ?
I think it's a dictionary implementation based on buckets (as any other decent dictionary implementation does...)
I've shown in my master thesis that a simple bucket-based dictionary can outperform our poor-mans single array collection dictionary in almost every operation. The only drawback is the slightly bigger size in memory.
On 2013-02-10, at 18:06, Sven Van Caekenberghe <sven@stfx.eu> wrote:
On 10 Feb 2013, at 17:07, Fernando Olivero <fernando.olivero@usi.ch> wrote:
Interesting, nice thesis Camilo. Why not replace Dictionary then? At least it should be integrated into Collections, in the image. Fernando
Yes, cool stuff, nice thesis; more stuff to readâ¦
If you did all this work, and it is provably better, then indeed, it should at least be an alternative in the collection framework.
BTW, regarding space, a dictionary that starts as a SmallDictionary internally and adjust itself according to usage would be ideal, the there is no price to pay.
This is what the dictionaries measured in my thesis do ;). We just start with one bucket, so you are slightly slower than a small dict due to 1 additional indirection, but you do no longer need a separate class for SmallDictionaries.
provide benchs and we will take adequate action :) Not you camillo :) Stef On Feb 10, 2013, at 5:07 PM, Fernando Olivero <fernando.olivero@usi.ch> wrote:
Interesting, nice thesis Camilo. Why not replace Dictionary then? At least it should be integrated into Collections, in the image. Fernando
On Sun, Feb 10, 2013 at 4:38 PM, Camillo Bruni <camillobruni@gmail.com> wrote:
On 2013-02-10, at 16:34, stephane ducasse <stephane.ducasse@free.fr> wrote:
On Feb 10, 2013, at 4:22 PM, Sven Van Caekenberghe <sven@stfx.eu> wrote:
On 10 Feb 2013, at 15:16, Stéphane Ducasse <stephane.ducasse@inria.fr> wrote:
- migrated all the history - defined configurationOf - All tests are green under 1.4 and 2.0
Stef
Dear I ask: what is HastTable and how it is different from Dictionary ?
I think it's a dictionary implementation based on buckets (as any other decent dictionary implementation does...)
I've shown in my master thesis that a simple bucket-based dictionary can outperform our poor-mans single array collection dictionary in almost every operation. The only drawback is the slightly bigger size in memory.
I can dig up all my benchmarks from my master ;) but I remember that we were faster on most operations or the same speed in the worst case. I have benchmarks for every possible case :P (that's a bit exaggerated), but there are 42 different micro benchmarks which stress most dictionary aspects. For operations like iterating over the keys/values of a dictionary we are 5 times faster (less overhead due to fixed structures) #includes on Set was also considerably faster in our implementation. On 2013-02-10, at 18:19, stephane ducasse <stephane.ducasse@free.fr> wrote:
provide benchs and we will take adequate action :)
Not you camillo :)
Stef
On Feb 10, 2013, at 5:07 PM, Fernando Olivero <fernando.olivero@usi.ch> wrote:
Interesting, nice thesis Camilo. Why not replace Dictionary then? At least it should be integrated into Collections, in the image. Fernando
On Sun, Feb 10, 2013 at 4:38 PM, Camillo Bruni <camillobruni@gmail.com> wrote:
On 2013-02-10, at 16:34, stephane ducasse <stephane.ducasse@free.fr> wrote:
On Feb 10, 2013, at 4:22 PM, Sven Van Caekenberghe <sven@stfx.eu> wrote:
On 10 Feb 2013, at 15:16, Stéphane Ducasse <stephane.ducasse@inria.fr> wrote:
- migrated all the history - defined configurationOf - All tests are green under 1.4 and 2.0
Stef
Dear I ask: what is HastTable and how it is different from Dictionary ?
I think it's a dictionary implementation based on buckets (as any other decent dictionary implementation does...)
I've shown in my master thesis that a simple bucket-based dictionary can outperform our poor-mans single array collection dictionary in almost every operation. The only drawback is the slightly bigger size in memory.
On Feb 11, 2013, at 1:34 PM, Camillo Bruni <camillobruni@gmail.com> wrote:
I can dig up all my benchmarks from my master ;) but I remember that we were faster on most operations or the same speed in the worst case. I have benchmarks for every possible case :P (that's a bit exaggerated), but there are 42 different micro benchmarks which stress most dictionary aspects.
For operations like iterating over the keys/values of a dictionary we are 5 times faster (less overhead due to fixed structures)
#includes on Set was also considerably faster in our implementation.
and of course degeneration due to the bad hashing should be much better handled⦠the current implementation, when it starts to have collision, it will make more collisions even more likely by using a free slot. And in case of collision, the buckets should be much faster to find something as with linear seating the entry can be much further away then just the number of colliding for one entry. Marcus
participants (5)
-
Camillo Bruni -
Fernando Olivero -
Marcus Denker -
stephane ducasse -
Sven Van Caekenberghe