I submitted my container library to code.dlang.org

w0rp via Digitalmars-d digitalmars-d at puremagic.com
Sun Mar 29 16:23:54 PDT 2015


On Sunday, 29 March 2015 at 22:32:34 UTC, Martin Nowak wrote:
> On 03/29/2015 05:19 PM, w0rp wrote:
>> 4. I ended up writing my own library hashmap, which when I 
>> tested ages
>> ago competed with the standard associative array in terms of
>> performance. This allows me to mark many things @safe pure 
>> nothrow.
>> 
>> Destroy!
>
> Nice docs.
>
> Always use open addressing when implementing a hash table.
> https://github.com/D-Programming-Language/dmd/pull/4088
> https://github.com/higgsjs/Higgs/pull/170

You probably beat my implementation in terms of speed now. I 
think the only thing
I did quite differently from the standard implementation was use 
& 2 for computing the hash index instead of a divide, as that was 
the method OpenJDK used for its hashmap.

>> Also, I was able to implement setDefault in a hopefully 
>> efficient
>> manner. I have tried to push setDefault as an awesome thing a 
>> few times,
>> but I've never been able to explain why it's good eloquently.
>
> I guess that's the counterpart to `get(key, default)` that also 
> inserts
> the default value. That's a very much needed primitive for our 
> AA,
> because currently you end up doing at least 1 unnecessary 
> lookup.
>
> Often I even write this.
>
> auto p = key in aa;
> if (p is null)
> {
>     aa[key] = default;
>     p = key in aa;
> }
>
> It's called getOrElseUpdate in Scala, but I'd prefer getOrSet.
> http://www.scala-lang.org/api/2.10.1-RC1/scala/collection/mutable/HashMap.html#getOrElseUpdate(A,⇒B):B

Yeah, that's the one. I personally don't really care what the 
name is. 'setdefault' is the Python name for it. Only we can do 
better than Python, because we have the lazy keyword. For which 
I'll say, "One magical day, the compiler can generate special 
code for this." As you say, it's special in that it has the 
ability to only compute the hash once when implemented with 
direct access to the hashtable.


More information about the Digitalmars-d mailing list