For anybody interested, I manage to improve performance up to ~2x slower than standard hash-map and pushed it to clojars.
https://github.com/frankiesardo/linked linked-set is still a bit slow so I'll keep investigating on it. On Tuesday, April 15, 2014 2:31:14 PM UTC+2, Frankie Sardo wrote: > > Thanks for the pointers Andy. > I had a look at the ordered-map and indeed is a smart and fast > implementation. However it relies on continuously growing a backing array, > filling dissoc-iated values with nil and hoping that at one point the user > will call (compact map) to free all the unused positions. In theory my > implementation should scale better as it only uses the space that it needs. > > However after more benchmarking I observed the following: > > - (assoc with multiple key-vals) does indeed slow down the operations. But > calling transient and persistent! only makes things worse with bigger maps > (I guess the whole map is copied before making it transient). > - There is quite a bottleneck due to querying 'head' and 'tail' on every > insertion. I thought the performance of a standard hash-map was definitely > better :) > > I could speed up the assoc performance avoiding the insertion of head and > tail inside the delegate-map and keeping those two nodes as class fields. > That won't make dissoc better but it seems like a reasonable compromise. > > Out of curiosity, is anybody using ordered-map in their projects? Since > performance is comparable to a standard hash-map I would always prefer to > use it for the deterministic ordering of the keys. Makes reproducing and > catching bugs/errors easier imho. > > > On Monday, April 14, 2014 10:48:48 PM UTC+2, Andy Fingerhut wrote: >> >> You may also want to take a look at the 'ordered' library, intended to >> achieve a similar affect as you describe of remembering elements in the >> order they were inserted. I don't know which of the two Github repos below >> is the current latest one, but it should be one of them: >> >> https://github.com/flatland/ordered >> https://github.com/amalloy/ordered >> >> Andy >> >> >> On Mon, Apr 14, 2014 at 12:36 PM, Andy Fingerhut <andy.fi...@gmail.com>wrote: >> >>> I don't have time right now to look at the details of your >>> implementation, but can answer at least one of your questions. >>> >>> Clojure's normal PersistentHashMap data structure does create a new >>> object for every key you remove (with dissoc), add, or modify the value for >>> (with assoc). So if a single assoc call is made that adds/changes the >>> values for 5 keys, 5 new PersistentHashMap objects will be created. >>> >>> That can be avoided if you call transient first, then assoc! N times >>> (each time on the result returned by the previous assoc!), then >>> persistent. There the assoc! calls still can create new objects, but they >>> will often simply edit the existing transient data structure in place. >>> These are a bit trickier to implement, so if I were you I would focus on >>> getting the persistent version correct and as fast as you can before >>> worrying about a transient version. Either that, or do not even both >>> creating a transient version at all. >>> >>> Andy >>> >>> >>> On Mon, Apr 14, 2014 at 11:59 AM, Frankie Sardo <fran....@gmail.com>wrote: >>> >>>> I'm on a mission to implement an ordered map and set structure for >>>> Clojure. Much like LinkedHashMap for Java but as a persistent data >>>> structure. >>>> The idea is that instead of saving a simple [k v] MapEntry we can save >>>> [k v left-node-key right-node-key] plus a global head-node-key to walk >>>> through the chains of nodes. >>>> Adding a new element creates a new node with a reference on the current >>>> tail and the head node and updates the tail and head node to reference the >>>> new key in the middle. >>>> Removing an element dissociates the selected node and associates the >>>> newly updated nodes at the left and the right of the removed one. >>>> >>>> What puzzles me is the overall performance of this data structure. >>>> While Big-O complexity is the same I knew it would be slower due to extra >>>> accesses to the inner map, but I expected to be close to the performance >>>> of a normal hash-map. Instead insertion is about 5x slower while the >>>> removal is 2x slower. So I wonder: is assoc-ing multiple keys at a time >>>> generating multiple persistent maps? Or am I doing something blatantly >>>> wrong here? >>>> >>>> However, if somebody'd like to have a look at it I pushed an initial >>>> version here https://github.com/frankiesardo/linked. Any help is much >>>> appreciated as I'm still a Clojure newbie. >>>> >>>> -- >>>> You received this message because you are subscribed to the Google >>>> Groups "Clojure" group. >>>> To post to this group, send email to clo...@googlegroups.com >>>> Note that posts from new members are moderated - please be patient with >>>> your first post. >>>> To unsubscribe from this group, send email to >>>> clojure+u...@googlegroups.com >>>> For more options, visit this group at >>>> http://groups.google.com/group/clojure?hl=en >>>> --- >>>> You received this message because you are subscribed to the Google >>>> Groups "Clojure" group. >>>> To unsubscribe from this group and stop receiving emails from it, send >>>> an email to clojure+u...@googlegroups.com. >>>> For more options, visit https://groups.google.com/d/optout. >>>> >>> >>> >> -- You received this message because you are subscribed to the Google Groups "Clojure" group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en --- You received this message because you are subscribed to the Google Groups "Clojure" group. To unsubscribe from this group and stop receiving emails from it, send an email to clojure+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/d/optout.
