faster than hashtable?

Hi,

If you need to store key/value pairs, where the key will be ALWAYS a
unique long (no collisions), is there anything better than a Hashtable?

Thanks

        pablo
_______________________________________________
Mono-devel-list mailing list
[hidden email]
http://lists.ximian.com/mailman/listinfo/mono-devel-list

[Tom Spink]

2009/10/27 [hidden email] <[hidden email]>:
> Hi,
>
> If you need to store key/value pairs, where the key will be ALWAYS a
> unique long (no collisions), is there anything better than a Hashtable?
>
> Thanks
>
>        pablo

Presumably, though, the key can span the entire range of a long?  If
it's an acceptably small range, you could use an array.

--
Tom Spink
_______________________________________________
Mono-devel-list mailing list
[hidden email]
http://lists.ximian.com/mailman/listinfo/mono-devel-list

[Alan McGovern]

If the key is random, a hashtable is the fastest way. You may be able to eke some extra speed out of the Dictionary<K, V> class by ripping all the code to support generic keys and instead hardcode the key to always be a long. That should save a bit of time, though whether it'd be noticable or not I don't know.

Alan.

On Wed, Oct 28, 2009 at 8:25 AM, Tom Spink <[hidden email]> wrote:

2009/10/27 [hidden email] <[hidden email]>:

> Hi,
>
> If you need to store key/value pairs, where the key will be ALWAYS a
> unique long (no collisions), is there anything better than a Hashtable?
>
> Thanks
>
>        pablo

Presumably, though, the key can span the entire range of a long?  If
it's an acceptably small range, you could use an array.

--
Tom Spink

_______________________________________________
Mono-devel-list mailing list
[hidden email]
http://lists.ximian.com/mailman/listinfo/mono-devel-list

_______________________________________________
Mono-devel-list mailing list
[hidden email]
http://lists.ximian.com/mailman/listinfo/mono-devel-list

[Oskar Berggren]

If you know your input set and can design a hash function that is
guaranteed to never give collisions for that input set, you could
perhaps gain something by implementing a hash table that ignores the
risk of collisions.

/Oskar


2009/10/28 Alan McGovern <[hidden email]>:

> If the key is random, a hashtable is the fastest way. You may be able to eke
> some extra speed out of the Dictionary<K, V> class by ripping all the code
> to support generic keys and instead hardcode the key to always be a long.
> That should save a bit of time, though whether it'd be noticable or not I
> don't know.
>
> Alan.
>
> On Wed, Oct 28, 2009 at 8:25 AM, Tom Spink <[hidden email]> wrote:
>>
>> 2009/10/27 [hidden email] <[hidden email]>:
>> > Hi,
>> >
>> > If you need to store key/value pairs, where the key will be ALWAYS a
>> > unique long (no collisions), is there anything better than a Hashtable?
>> >
>> > Thanks
>> >
>> >        pablo
>>
>> Presumably, though, the key can span the entire range of a long?  If
>> it's an acceptably small range, you could use an array.
>>
>> --
>> Tom Spink
>> _______________________________________________
>> Mono-devel-list mailing list
>> [hidden email]
>> http://lists.ximian.com/mailman/listinfo/mono-devel-list
>
>
> _______________________________________________
> Mono-devel-list mailing list
> [hidden email]
> http://lists.ximian.com/mailman/listinfo/mono-devel-list
>
>

_______________________________________________
Mono-devel-list mailing list
[hidden email]
http://lists.ximian.com/mailman/listinfo/mono-devel-list

Thanks,

Good to know! I'll give it a try.

Alan McGovern wrote:

> If the key is random, a hashtable is the fastest way. You may be able to
> eke some extra speed out of the Dictionary<K, V> class by ripping all
> the code to support generic keys and instead hardcode the key to always
> be a long. That should save a bit of time, though whether it'd be
> noticable or not I don't know.
>
> Alan.
>
> On Wed, Oct 28, 2009 at 8:25 AM, Tom Spink <[hidden email]
> <mailto:[hidden email]>> wrote:
>
>     2009/10/27 [hidden email]
>     <mailto:[hidden email]> <[hidden email]
>     <mailto:[hidden email]>>:
>     > Hi,
>     >
>     > If you need to store key/value pairs, where the key will be ALWAYS a
>     > unique long (no collisions), is there anything better than a
>     Hashtable?
>     >
>     > Thanks
>     >
>     >        pablo
>
>     Presumably, though, the key can span the entire range of a long?  If
>     it's an acceptably small range, you could use an array.
>
>     --
>     Tom Spink
>     _______________________________________________
>     Mono-devel-list mailing list
>     [hidden email]
>     <mailto:[hidden email]>
>     http://lists.ximian.com/mailman/listinfo/mono-devel-list
>
>
>
> ------------------------------------------------------------------------
>
> _______________________________________________
> Mono-devel-list mailing list
> [hidden email]
> http://lists.ximian.com/mailman/listinfo/mono-devel-list

_______________________________________________
Mono-devel-list mailing list
[hidden email]
http://lists.ximian.com/mailman/listinfo/mono-devel-list

[Felipe Lessa]

On Tue, Oct 27, 2009 at 11:58:31PM +0100, [hidden email] wrote:
> If you need to store key/value pairs, where the key will be ALWAYS a
> unique long (no collisions), is there anything better than a Hashtable?

There are always Judy arrays, see http://judy.sourceforge.net/.

--
Felipe.
_______________________________________________
Mono-devel-list mailing list
[hidden email]
http://lists.ximian.com/mailman/listinfo/mono-devel-list

Excellent. Is there a wrapper for C#? Is it worth?

Felipe Lessa wrote:

> On Tue, Oct 27, 2009 at 11:58:31PM +0100, [hidden email] wrote:
>> If you need to store key/value pairs, where the key will be ALWAYS a
>> unique long (no collisions), is there anything better than a Hashtable?
>
> There are always Judy arrays, see http://judy.sourceforge.net/.
>
> --
> Felipe.
> _______________________________________________
> Mono-devel-list mailing list
> [hidden email]
> http://lists.ximian.com/mailman/listinfo/mono-devel-list
>

_______________________________________________
Mono-devel-list mailing list
[hidden email]
http://lists.ximian.com/mailman/listinfo/mono-devel-list

[Alan McGovern]

Really what you need to do is benchmark all of the different options using your expected workload. It's near useless us telling you X is faster or Y is better without knowing the workload involved.

Alan.

On Wed, Oct 28, 2009 at 2:40 PM, [hidden email] <[hidden email]> wrote:

Excellent. Is there a wrapper for C#? Is it worth?

Felipe Lessa wrote:
> On Tue, Oct 27, 2009 at 11:58:31PM +0100, [hidden email] wrote:
>> If you need to store key/value pairs, where the key will be ALWAYS a
>> unique long (no collisions), is there anything better than a Hashtable?
>
> There are always Judy arrays, see http://judy.sourceforge.net/.
>
> --
> Felipe.
> _______________________________________________
> Mono-devel-list mailing list
> [hidden email]
> http://lists.ximian.com/mailman/listinfo/mono-devel-list
>
_______________________________________________
Mono-devel-list mailing list
[hidden email]
http://lists.ximian.com/mailman/listinfo/mono-devel-list

_______________________________________________
Mono-devel-list mailing list
[hidden email]
http://lists.ximian.com/mailman/listinfo/mono-devel-list

[Felipe Lessa]

On Wed, Oct 28, 2009 at 12:40 PM, [hidden email]
<[hidden email]> wrote:
> Excellent. Is there a wrapper for C#? Is it worth?

Not that I know of, however it shouldn't be hard to create one.

--
Felipe.
_______________________________________________
Mono-devel-list mailing list
[hidden email]
http://lists.ximian.com/mailman/listinfo/mono-devel-list

Sure Alan!

So, basically, the options are:

- Use a sorted ArrayList and a binary search
- Reimplement hashtable focusing on long keys
- Write a wrapper to Judy

Alan McGovern wrote:

> Really what you need to do is benchmark all of the different options
> using your expected workload. It's near useless us telling you X is
> faster or Y is better without knowing the workload involved.
>
> Alan.
>
> On Wed, Oct 28, 2009 at 2:40 PM, [hidden email]
> <mailto:[hidden email]> <[hidden email]
> <mailto:[hidden email]>> wrote:
>
>     Excellent. Is there a wrapper for C#? Is it worth?
>
>     Felipe Lessa wrote:
>     > On Tue, Oct 27, 2009 at 11:58:31PM +0100,
>     [hidden email] <mailto:[hidden email]> wrote:
>     >> If you need to store key/value pairs, where the key will be ALWAYS a
>     >> unique long (no collisions), is there anything better than a
>     Hashtable?
>     >
>     > There are always Judy arrays, see http://judy.sourceforge.net/.
>     >
>     > --
>     > Felipe.
>     > _______________________________________________
>     > Mono-devel-list mailing list
>     > [hidden email]
>     <mailto:[hidden email]>
>     > http://lists.ximian.com/mailman/listinfo/mono-devel-list
>     >
>     _______________________________________________
>     Mono-devel-list mailing list
>     [hidden email]
>     <mailto:[hidden email]>
>     http://lists.ximian.com/mailman/listinfo/mono-devel-list
>
>

_______________________________________________
Mono-devel-list mailing list
[hidden email]
http://lists.ximian.com/mailman/listinfo/mono-devel-list

[Alan McGovern]

Hey,

On Wed, Oct 28, 2009 at 4:30 PM, [hidden email] <[hidden email]> wrote:

Sure Alan!

So, basically, the options are:

- Use a sorted ArrayList and a binary search

For this option the same story applies as for Dictionary <K,V>. If you write a strongly typed sorted list where the key is hardcoded as long, you might be able to gain a few % in performance. It depends on whether the extra %'s (if any) are worth the increased maintainer burden. If this is a super-critical lookup, then it might be worth it.

- Reimplement hashtable focusing on long keys
- Write a wrapper to Judy

Alan.

Alan McGovern wrote:
> Really what you need to do is benchmark all of the different options
> using your expected workload. It's near useless us telling you X is
> faster or Y is better without knowing the workload involved.
>
> Alan.
>
> On Wed, Oct 28, 2009 at 2:40 PM, [hidden email]

> <mailto:[hidden email]> <[hidden email]

> <mailto:[hidden email]>> wrote:
>
>     Excellent. Is there a wrapper for C#? Is it worth?
>
>     Felipe Lessa wrote:
>     > On Tue, Oct 27, 2009 at 11:58:31PM +0100,

>     [hidden email] <mailto:[hidden email]> wrote:
>     >> If you need to store key/value pairs, where the key will be ALWAYS a
>     >> unique long (no collisions), is there anything better than a
>     Hashtable?
>     >
>     > There are always Judy arrays, see http://judy.sourceforge.net/.
>     >
>     > --
>     > Felipe.
>     > _______________________________________________
>     > Mono-devel-list mailing list
>     > [hidden email]

>     <mailto:[hidden email]>

>     > http://lists.ximian.com/mailman/listinfo/mono-devel-list
>     >
>     _______________________________________________
>     Mono-devel-list mailing list
>     [hidden email]

>     <mailto:[hidden email]>

>     http://lists.ximian.com/mailman/listinfo/mono-devel-list
>
>

_______________________________________________
Mono-devel-list mailing list
[hidden email]
http://lists.ximian.com/mailman/listinfo/mono-devel-list

[Rafael Teixeira]

As p/invokes cost a lot, another (fourth) option would be to
reimplement judy arrays algorithm (which I admittedly know nearly
nothing about) in managed code. From reading their 10 minutes intro, I
guess some of the cache-fill optimizations it implements may be
jeopardized by the JIT workings, but I guess it still may be helpful
to implement and profile along the other options.

Hope it helps,

Rafael "Monoman" Teixeira
---------------------------------------
"To be creative means to be in love with life. You can be creative
only if you love life enough that you want to enhance its beauty, you
want to bring a little more music to it, a little more poetry to it, a
little more dance to it."
Osho



On Wed, Oct 28, 2009 at 2:30 PM, [hidden email]
<[hidden email]> wrote:

> Sure Alan!
>
> So, basically, the options are:
>
> - Use a sorted ArrayList and a binary search
> - Reimplement hashtable focusing on long keys
> - Write a wrapper to Judy
>
> Alan McGovern wrote:
>> Really what you need to do is benchmark all of the different options
>> using your expected workload. It's near useless us telling you X is
>> faster or Y is better without knowing the workload involved.
>>
>> Alan.
>>
>> On Wed, Oct 28, 2009 at 2:40 PM, [hidden email]
>> <mailto:[hidden email]> <[hidden email]
>> <mailto:[hidden email]>> wrote:
>>
>>     Excellent. Is there a wrapper for C#? Is it worth?
>>
>>     Felipe Lessa wrote:
>>     > On Tue, Oct 27, 2009 at 11:58:31PM +0100,
>>     [hidden email] <mailto:[hidden email]> wrote:
>>     >> If you need to store key/value pairs, where the key will be ALWAYS a
>>     >> unique long (no collisions), is there anything better than a
>>     Hashtable?
>>     >
>>     > There are always Judy arrays, see http://judy.sourceforge.net/.
>>     >
>>     > --
>>     > Felipe.
>>     > _______________________________________________
>>     > Mono-devel-list mailing list
>>     > [hidden email]
>>     <mailto:[hidden email]>
>>     > http://lists.ximian.com/mailman/listinfo/mono-devel-list
>>     >
>>     _______________________________________________
>>     Mono-devel-list mailing list
>>     [hidden email]
>>     <mailto:[hidden email]>
>>     http://lists.ximian.com/mailman/listinfo/mono-devel-list
>>
>>
> _______________________________________________
> Mono-devel-list mailing list
> [hidden email]
> http://lists.ximian.com/mailman/listinfo/mono-devel-list
>

_______________________________________________
Mono-devel-list mailing list
[hidden email]
http://lists.ximian.com/mailman/listinfo/mono-devel-list

[Konstantin Triger]

You may also consider using "bit dictionary algorythms":

Suppose your key is n bits long, you divide it to k levels each m bits (k*m = n).

At each level you have 2^m arrays that point to the next level array etc, while at last it will be an array of values. Provided the range of potential keys is relatively dense this solution will not take too much memory, while read access will be very fast since it's only several bit operations and memory dereferences.

Kosta

On Wed, Oct 28, 2009 at 7:10 PM, Rafael Teixeira <[hidden email]> wrote:

As p/invokes cost a lot, another (fourth) option would be to
reimplement judy arrays algorithm (which I admittedly know nearly
nothing about) in managed code. From reading their 10 minutes intro, I
guess some of the cache-fill optimizations it implements may be
jeopardized by the JIT workings, but I guess it still may be helpful
to implement and profile along the other options.

Hope it helps,

Rafael "Monoman" Teixeira
---------------------------------------
"To be creative means to be in love with life. You can be creative
only if you love life enough that you want to enhance its beauty, you
want to bring a little more music to it, a little more poetry to it, a
little more dance to it."
Osho

On Wed, Oct 28, 2009 at 2:30 PM, [hidden email]
<[hidden email]> wrote:
> Sure Alan!
>
> So, basically, the options are:
>
> - Use a sorted ArrayList and a binary search
> - Reimplement hashtable focusing on long keys
> - Write a wrapper to Judy
>
> Alan McGovern wrote:
>> Really what you need to do is benchmark all of the different options
>> using your expected workload. It's near useless us telling you X is
>> faster or Y is better without knowing the workload involved.
>>
>> Alan.
>>
>> On Wed, Oct 28, 2009 at 2:40 PM, [hidden email]
>> <mailto:[hidden email]> <[hidden email]
>> <mailto:[hidden email]>> wrote:
>>
>>     Excellent. Is there a wrapper for C#? Is it worth?
>>
>>     Felipe Lessa wrote:
>>     > On Tue, Oct 27, 2009 at 11:58:31PM +0100,
>>     [hidden email] <mailto:[hidden email]> wrote:
>>     >> If you need to store key/value pairs, where the key will be ALWAYS a
>>     >> unique long (no collisions), is there anything better than a
>>     Hashtable?
>>     >
>>     > There are always Judy arrays, see http://judy.sourceforge.net/.
>>     >
>>     > --
>>     > Felipe.
>>     > _______________________________________________
>>     > Mono-devel-list mailing list
>>     > [hidden email]
>>     <mailto:[hidden email]>
>>     > http://lists.ximian.com/mailman/listinfo/mono-devel-list
>>     >
>>     _______________________________________________
>>     Mono-devel-list mailing list
>>     [hidden email]
>>     <mailto:[hidden email]>
>>     http://lists.ximian.com/mailman/listinfo/mono-devel-list
>>
>>
> _______________________________________________
> Mono-devel-list mailing list
> [hidden email]
> http://lists.ximian.com/mailman/listinfo/mono-devel-list
>
_______________________________________________
Mono-devel-list mailing list
[hidden email]
http://lists.ximian.com/mailman/listinfo/mono-devel-list

--
Regards,
Konstantin Triger
RSS: http://feeds.feedburner.com/ktriger

_______________________________________________
Mono-devel-list mailing list
[hidden email]
http://lists.ximian.com/mailman/listinfo/mono-devel-list