HashTable

[Helge Jensen]

Re: HashTable

Dennis Myrén wrote:[color=blue]
> Thank you, Helge.[/color]

No problemo.
[color=blue]
> I have done all changes you suggested except in get_Values.[/color]

Don't accept my advice as definitive, run your benchmarks and see if
things change, and in what direction :)

Optimizing code-structure to suit the compiler is often a guessing-game.
For example I wrote 4 different implementations of an interpreter for a
small language: iterative, recursive and
multiple-tailrecursive-functions(passi ng the state in an "accumulato r"),
which was the fastest do you think?

HINT: gcc and MSVC6 produced the fastest code on one of them, MSVC7 on
another.
[color=blue]
> The reason of the Add method of signature:
> Add ( ref int, ref int, bool )
> is that it is a private method used internally only.
> I use ref to prevent a copy of the Int32 being made, doing what i can to
> gain performance.[/color]

Off the top of my head I would doubt that you are getting any benefit
from the ref's, Does your benchmarks show a performance gain from it?

--
Helge

[Dennis Myrén]

Re: HashTable

Helge and Richard,
Yes you are absolutely right, i probably do not earn anything(in this
particular case of Int32)
using ref.
I decided to remove the internal Add method, resulting in 10 more lines of
code
but saving a method call and an if statement. It is getting quick now.
Now i have an average access time for a million slots of 30ms, compared
to System.COllecti ons.Hashtable's 380ms.
That is a greater benefit than i would ever imagine.
Have you done any benchmarks on it? Please give me your results in that
case.
I once again updated the ZIP:

http://dev.oslokb.no:8080/dennis/widgets/Int32Hashtable.zip

if you are interested.

And Helge, I would guess that the iterative approach was your fastest
implementation?

--
Regards,
Dennis JD Myrén
Oslo Kodebureau
"Dennis Myrén" <dennis@oslokb. no> wrote in message
news:FvNHd.5251 $IW4.107733@new s2.e.nsc.no...[color=blue]
> Thank you, Helge.
> I have done all changes you suggested except in get_Values.
> The ZIP is updated:
> http://dev.oslokb.no:8080/dennis/wid...2Hashtable.zip
>
> The reason of the Add method of signature:
> Add ( ref int, ref int, bool )
> is that it is a private method used internally only.
> I use ref to prevent a copy of the Int32 being made, doing what i can to
> gain performance.
>
> --
> Regards,
> Dennis JD Myrén
> Oslo Kodebureau
> "Helge Jensen" <helge.jensen@s log.dk> wrote in message
> news:OR2Maku$EH A.3120@TK2MSFTN GP12.phx.gbl...[color=green]
>>[color=darkred]
>>> Please let me know of any eventual bugs you might find.[/color]
>>
>> Here are a few things that jumped into my eyes:
>>
>> * try/catch:
>>
>> try
>> {
>> return _host [_keys [_i]];
>> }
>> catch (System.IndexOu tOfRangeExcepti on e)
>> {
>> throw e;
>> }
>>
>> Could be written just as:
>>
>> return _host [_keys [_i]];
>>
>> There is really no good reason to catch an rethrow that exception, is
>> there?
>>
>> If you need to do some work on the way out in a callstack, you can use
>> finally, or when you need to use the Exception (for logging for example),
>> using "throw" instead of "throw e" preserves the original stacktrace.
>>
>> * Enumerator:
>>
>> You define enumeration to be sorted, there is no reason for that, the
>> basic iteration of hashtables or dictionaries are not guranteed to be
>> sorted, sorting is expensive (in this context where operations are O(1)
>> :) and requires you to spen O(capacity) memory, which is pretty much for
>> large hashed.
>>
>> To do sorted iteration, the user can easily do:
>>
>> int[] keys = new int[dict.Count]
>> dict.keys.CopyT o(keys, 0);
>> foreach ( int key in keys ) {
>> object val = dict[key];
>> }
>>
>> or you can define a class SortedCollectio n that accepts an ICollection
>> and provides sorted Enumeration.
>>
>> * indexing:
>>
>> why do your do "& int.MaxValue"?
>>
>> int i = (key & int.MaxValue) % _slots.Length;
>>
>> Rather than
>>
>> int index = (uint)key % _slots.Length;
>>
>> It's less expensive, and doesn't disregard the most-significant bit of
>> your key
>>
>> * .Values
>>
>> Return a new instance of ICollection that simply iterates the hashtable,
>> returning only the keys. This saves a lot of memory.
>>
>> If the user want's an array he can do dict.Values.Cop yTo(array, index).
>>
>> * int this[int key] { set }
>>
>> * Add(key, value, overwrite)
>>
>> Why do you accept ref's to key and value?
>>
>> * Clear:
>>
>> use the System.Array methods for clearing an array, or simple assign a
>> new array to _slots
>>
>> --
>> Helge[/color]
>
>[/color]