Clojurians
#cljs-dev
<
2015-11-12
>

This page is not created by, affiliated with, or supported by Slack Technologies, Inc.

spinningtopsofdoom19:11:52

@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.

dnolen19:11:29

@spinningtopsofdoom: make sure you are using dense arrays only

dnolen19:11:51

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

dnolen19:11:59

this is how ClojureScript does it

spinningtopsofdoom19:11:51

That's with the make-array function correct?

dnolen19:11:03

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

dnolen19:11:11

you really want it to be

dnolen19:11:15

this has to be done inline

dnolen19:11:33

huge perf difference creating these things inline

spinningtopsofdoom19:11:06

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

dnolen19:11:15

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

dnolen19:11:21

(make-array 32) does the right thing

dnolen19:11:40

you will have a truth call

dnolen19:11:56

you need a ^boolean hint on can-edit

dnolen19:11:04

line 35 you’re not using key-test

dnolen19:11:06

maybe intentional?

dnolen19:11:38

boolean issues

spinningtopsofdoom19:11:00

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

spinningtopsofdoom19:11:42

thanks for all the help!

dnolen19:11:52

the boolean tests are killer

dnolen19:11:58

if they are on the critical path

dnolen19:11:03

perf is completely hosed

dnolen19:11:10

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

spinningtopsofdoom19:11:29

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

dnolen19:11:56

probably quite a bit

dnolen19:11:05

but I know @alexmiller is interested in this too

spinningtopsofdoom19:11:13

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

dnolen19:11:21

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

dnolen19:11:32

but this data structure is probably best as a contrib

spinningtopsofdoom19:11:03

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

dnolen19:11:36

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

dnolen19:11:12

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

dnolen19:11:14

looks cool

dnolen19:11:27

I’m helping sort out the obvious perf issues

alexmiller19:11:50

Rich gave me the ok to investigate some of that

alexmiller19:11:20

I was hoping to do so in 1.9 context

dnolen19:11:23

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

dnolen19:11:26

which is promising

alexmiller19:11:09

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

spinningtopsofdoom19:11:15

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

spinningtopsofdoom19:11:54

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

dnolen19:11:05

cool stuff! excited about it

alexmiller19:11:49

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

spinningtopsofdoom20:11:58

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

alexmiller20:11:42

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

spinningtopsofdoom20:11:31

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.

spinningtopsofdoom20:11:29

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

spinningtopsofdoom20:11:47

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.

alexmiller20:11:59

no worries, just curious

dnolen20:11:36

@alexmiller: it does matter

dnolen20:11:05

modern JS engines have a dizzying set of array types

dnolen20:11:24

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

dnolen20:11:04

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

dnolen20:11:37

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

dnolen20:11:46

now in the JVM ballpark for HAMT perf

martinklepsch22:11:44

@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 :simple_smile:

spinningtopsofdoom22:11:41

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

spinningtopsofdoom22:11:28

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

martinklepsch22:11:10

@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

spinningtopsofdoom22:11:49

Thanks you very much I'm heading out now.

martinklepsch23:11:41

@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

martinklepsch23:11:53

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