@dnolen: I've got a rough port of the Lean Hash Array Map Trie (https://github.com/bendyworks/lean-map) done. All the basic HashMap functionality is there and it runs ~25% slower then the current implementation. I'm currently going through bugs I've found via property checking.

@spinningtopsofdoom: make sure you are using dense arrays only

the only way to guarantee this in a reliable way across JS engines is to make an array initialized to null of the dimension you desire

this is how ClojureScript does it

That's with the make-array function correct?

I don’t recall if make-array is a macro let me check

you really want it to be

this has to be done inline

huge perf difference creating these things inline

ok yes

So for making a node I'd want the array to be 32 null 's ?

@spinningtopsofdoom: here’s a quick review of your code

(make-array 32) does the right thing

line 51

you will have a truth call

you need a ^boolean hint on can-edit

line 35 you’re not using key-test

maybe intentional?

149 too

200 & 201

boolean issues

no simple over sight I've working on getting this working then making it fast

thanks for all the help!

the boolean tests are killer

if they are on the critical path

perf is completely hosed

boolean tests (cljs.core.truth_) always mean an expensive check as well as often a closure allocation

What level of perf and testing would be needed for this to even come close to replacing the current implementation of HashMap?

probably quite a bit

but I know @alexmiller is interested in this too

Ouch I knew they were a perf hit but not that bad

if we could prove that it’s faster on JavaScript then a good reason to also pursue on Java

but this data structure is probably best as a contrib

Yeah that's my thoughts too but one can dream.

aroo?

I mean if it turns out to be faster on JS and JVM I don’t see why we wouldn’t replace

@alexmiller: @spinningtopsofdoom of is working on porting the new HAMT paper to ClojureScript

looks cool

I’m helping sort out the obvious perf issues

ah cool

Rich gave me the ok to investigate some of that

I was hoping to do so in 1.9 context

@alexmiller: @spinningtopsofdoom is 25% of ClojureScript HAMT even with glaring perf issues

which is promising

I think some of it makes total sense and the rest probably does too, just need to look at it closer

Another win is it needs less code and less complex code (at least from the very rough port I've done so far)

thanks again for all you help @dnolen I'll let you and @alexmiller know if anything interesting comes from this experiment

cool stuff! excited about it

please do

do things like object layout memory concerns translate to js env?

Do you mean in terms of iteration and cache misses or the size of the datasctructure on heap?

size

I just don't know enough about js to know whether those things translate or not

hmmm I'd image that there would be memory savings from removing the nil's as markers for nodes. IIRC js arrays size themselves based on what they store.

i.e. if you have an array of all integers it'll be more compact then any array of objects.

I know some of what happens behind the scenes in JS land when it comes to memory layout but not enough to definitively answer your question.

no worries, just curious

@alexmiller: it does matter

modern JS engines have a dizzying set of array types

they try to determine at runtime whether a JS array is really unboxed integers or whatever

and you really have to be careful to make sure you get those as well as dense arrays

I fixed this in CLJS HAMTs a couple of years ago - 3-4X perf enhancement across all major JS engines

now in the JVM ballpark for HAMT perf

@spinningtopsofdoom: hey, I saw you’re using some code very close to ztellman/collection-check — did you make any further modifications besides adaptions for cljs? I’m pretty close to done porting it, if you feel like giving it a spin

That would be awesome could you point me to the repo? The collection check doesn't show me the minimal case for some reason 😞

I basically copy pasta'd and stopped when I got ClojureScripts HashMap's passing the tests

@spinningtopsofdoom: it’s at https://github.com/martinklepsch/collection-check-1 but there is a bunch of uncommitted stuff, will ping you when I pushed

Thanks you very much I'm heading out now.

@spinningtopsofdoom: pushed. to install to local ~/.m2 you need to run boot build-jar, if you don’t have boot installed: https://github.com/boot-clj/boot#install

@spinningtopsofdoom: just realized that the minimal case stuff is also not properly shown with the cljc version