Migrated HashTable from ss to SmalltalkHub

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
12 messages Options
Reply | Threaded
Open this post in threaded view
|

Migrated HashTable from ss to SmalltalkHub

Stéphane Ducasse
- migrated all the history
- defined configurationOf
- All tests are green under 1.4 and 2.0

Stef

Reply | Threaded
Open this post in threaded view
|

Re: Migrated HashTable from ss to SmalltalkHub

Sven Van Caekenberghe-2

On 10 Feb 2013, at 15:16, Stéphane Ducasse <[hidden email]> 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 ?


Reply | Threaded
Open this post in threaded view
|

Re: Migrated HashTable from ss to SmalltalkHub

camille teruel
On 10 févr. 2013, at 16:22, Sven Van Caekenberghe wrote:

>
> On 10 Feb 2013, at 15:16, Stéphane Ducasse <[hidden email]> 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 ?

Not sure but I think it's an implementation with proper collision management.
Reply | Threaded
Open this post in threaded view
|

Re: Migrated HashTable from ss to SmalltalkHub

stephane ducasse
In reply to this post by Sven Van Caekenberghe-2

On Feb 10, 2013, at 4:22 PM, Sven Van Caekenberghe <[hidden email]> wrote:

>
> On 10 Feb 2013, at 15:16, Stéphane Ducasse <[hidden email]> 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 ?

No idea :)
Fame uses it so I moved it.
Tests are green and all the history is now migrated.

Stef
Reply | Threaded
Open this post in threaded view
|

Re: Migrated HashTable from ss to SmalltalkHub

Camillo Bruni-3

On 2013-02-10, at 16:34, stephane ducasse <[hidden email]> wrote:

>
> On Feb 10, 2013, at 4:22 PM, Sven Van Caekenberghe <[hidden email]> wrote:
>
>>
>> On 10 Feb 2013, at 15:16, Stéphane Ducasse <[hidden email]> 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.

http://scg.unibe.ch/archive/masters/Brun11a.pdf
Reply | Threaded
Open this post in threaded view
|

Re: Migrated HashTable from ss to SmalltalkHub

Fernando olivero-2
In reply to this post by stephane ducasse
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 <[hidden email]> wrote:

On 2013-02-10, at 16:34, stephane ducasse <[hidden email]> wrote:

>
> On Feb 10, 2013, at 4:22 PM, Sven Van Caekenberghe <[hidden email]> wrote:
>
>>
>> On 10 Feb 2013, at 15:16, Stéphane Ducasse <[hidden email]> 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.

http://scg.unibe.ch/archive/masters/Brun11a.pdf

Reply | Threaded
Open this post in threaded view
|

Re: Migrated HashTable from ss to SmalltalkHub

Camillo Bruni-3

On 2013-02-10, at 17:07, Fernando Olivero <[hidden email]> 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.


Reply | Threaded
Open this post in threaded view
|

Re: Migrated HashTable from ss to SmalltalkHub

Sven Van Caekenberghe-2
In reply to this post by Fernando olivero-2

On 10 Feb 2013, at 17:07, Fernando Olivero <[hidden email]> 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 <[hidden email]> wrote:
>
> On 2013-02-10, at 16:34, stephane ducasse <[hidden email]> wrote:
>
> >
> > On Feb 10, 2013, at 4:22 PM, Sven Van Caekenberghe <[hidden email]> wrote:
> >
> >>
> >> On 10 Feb 2013, at 15:16, Stéphane Ducasse <[hidden email]> 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.
>
> http://scg.unibe.ch/archive/masters/Brun11a.pdf
>


Reply | Threaded
Open this post in threaded view
|

Re: Migrated HashTable from ss to SmalltalkHub

Camillo Bruni-3

On 2013-02-10, at 18:06, Sven Van Caekenberghe <[hidden email]> wrote:

>
> On 10 Feb 2013, at 17:07, Fernando Olivero <[hidden email]> 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.
Reply | Threaded
Open this post in threaded view
|

Re: Migrated HashTable from ss to SmalltalkHub

stephane ducasse
In reply to this post by Fernando olivero-2
provide benchs and we will take adequate action :)

Not you camillo :)

Stef

On Feb 10, 2013, at 5:07 PM, Fernando Olivero <[hidden email]> 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 <[hidden email]> wrote:

On 2013-02-10, at 16:34, stephane ducasse <[hidden email]> wrote:

>
> On Feb 10, 2013, at 4:22 PM, Sven Van Caekenberghe <[hidden email]> wrote:
>
>>
>> On 10 Feb 2013, at 15:16, Stéphane Ducasse <[hidden email]> 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.

http://scg.unibe.ch/archive/masters/Brun11a.pdf


Reply | Threaded
Open this post in threaded view
|

Re: Migrated HashTable from ss to SmalltalkHub

Camillo Bruni-3
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 <[hidden email]> wrote:

> provide benchs and we will take adequate action :)
>
> Not you camillo :)
>
> Stef
>
> On Feb 10, 2013, at 5:07 PM, Fernando Olivero <[hidden email]> 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 <[hidden email]> wrote:
>>
>> On 2013-02-10, at 16:34, stephane ducasse <[hidden email]> wrote:
>>
>>>
>>> On Feb 10, 2013, at 4:22 PM, Sven Van Caekenberghe <[hidden email]> wrote:
>>>
>>>>
>>>> On 10 Feb 2013, at 15:16, Stéphane Ducasse <[hidden email]> 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.
>>
>> http://scg.unibe.ch/archive/masters/Brun11a.pdf
>>
>


Reply | Threaded
Open this post in threaded view
|

Re: Migrated HashTable from ss to SmalltalkHub

Marcus Denker-4

On Feb 11, 2013, at 1:34 PM, Camillo Bruni <[hidden email]> 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