Both, actually. The algorithm incrementally builds a tree via simulation. There's a step of traversing the current version of the tree to find a leaf, which requires immutability, as I have to remember the path taken (the path is generated via simulation, not by walking an existing tree structure, so requires updates to the state maps). But once at a leaf, I run multiple simulations in parallel, and provided each starts with an independent mutable "copy", then the subsequent states can be mutable. That should be a big perf win, since it's where the algo spends a lot of it's time. The data structures that hold the statistics about the states in the tree could also be mutable. These are keyed by state maps, hoping improved hash/equality performance will help a little there as well.
On Sunday, April 23, 2017 at 1:18:56 PM UTC-7, Zach Tellman wrote: > > Are you relying on the immutability of these structures, or are they > effectively always transient? > On Sun, Apr 23, 2017 at 11:02 AM Dave Dixon <dave.d...@gmail.com > <javascript:>> wrote: > >> FWIW, the use-case I have essentially involves Monte Carlo simulations. >> So we start with a state (non-empty map), and then make a series of >> modifications to it. Various statistics are held in hash-maps keyed by the >> state, so there's a lot of lookups and modifications in those maps. >> >> That said, I'm not sure if for this particular case I care too much using >> Clojure idioms vs. direct API access. The algorithms tend to be >> hand-tweaked for performance anyway. The big win for me in wrapping >> bifurcan would be the ability to use spec without having to write >> specialized specs, generators, etc. >> >> >> On Thursday, April 20, 2017 at 9:53:56 PM UTC-7, Zach Tellman wrote: >> >>> Sure, happy to elaborate. Bifurcan offers potential performance wins a >>> few different ways: >>> >>> * We can use standard Java equality semantics, bypassing all the >>> overhead of the hash calculations and enhanced numeric equality checks >>> (this can lead to moderate performance gains) >>> * We can use a mutable data structure as long as it never escapes a >>> local context (this can lead to significant performance gains) >>> * We can use the extra capabilities the data structures expose, like >>> concatenation, slicing, set operations, etc. (this is too dependent on the >>> use case to really quantify) >>> >> >>> it would be easy to have a `map` and `map*` method that expose Clojure >>> and Java equality semantics, respectively, but that puts a big onus on the >>> developer to determine if the latter is safe for their use case. I've been >>> bit by this when I've used j.u.c.ConcurrentHashMap before, so I expect >>> people will suffer similarly weird bugs. >>> >>> However, I think there's a way to use the mutable data structures. >>> Technically, transient data structures allow arbitrary persistent data >>> structures to be batch updated, but in practice they tend to be empty, and >>> after they're populated they tend to be treated as read-only. >>> >>> If we're convinced this is common enough, every empty transient data >>> structure could be mutable, and when we make it persistent we could wrap it >>> in a "virtual" collection [1] which allows updates without touching the >>> base collection. This would allow for faster writes, faster reads, and >>> only marginally slower updates if those are required. >>> >>> This is all predicated on a bunch of assumptions that are hard to >>> validate, but if this describes enough real-world use cases, it could lead >>> to a big, easy performance win. It's even possible to automatically >>> replace the base Clojure collections with these alternatives using >>> something like Sleight [2]. >>> >>> Anyway, that's what I've been mulling over. If anyone has opinions, I'm >>> happy to hear them. >>> >>> Zach >>> >>> [1] >>> https://github.com/lacuna/bifurcan/blob/master/src/io/lacuna/bifurcan/Maps.java#L103 >>> [2] https://github.com/ztellman/sleight >>> >>> On Thu, Apr 20, 2017 at 8:55 AM Dave Dixon <dave.d...@gmail.com> wrote: >>> >>>> Sounds great. If you have time, I'd certainly like to hear your >>>> thoughts on the issues of equality semantics and transients, maybe I can >>>> ponder and make some suggestions based on my target use-case. >>>> >>>> >>>> On Tuesday, April 18, 2017 at 9:32:32 AM UTC-7, Zach Tellman wrote: >>>> >>>>> To be clear, my intention was always to wrap the implementations in >>>>> the appropriate Clojure interfaces, and I don't believe that will cause >>>>> much, if any, of a performance hit (inlining is magic). However, there >>>>> are >>>>> some real questions regarding how to expose non-standard equality >>>>> semantics, and whether transients should be represented using the >>>>> immutable >>>>> or mutable collection variants. >>>>> >>>>> For what it's worth, I have about 1/3 of an implementation of >>>>> Clojure-compatible versions of these data structures, I just wanted to >>>>> mull >>>>> on the above questions a bit before going further. I'm happy to discuss >>>>> them here in more depth if you have any questions or opinions. >>>>> >>>>> Zach >>>>> >>>>> On Tue, Apr 18, 2017 at 6:53 AM Dave Dixon <dave.d...@gmail.com> >>>>> wrote: >>>>> >>>> Stared at this a bit yesterday. Seems like if you want to leverage spec >>>>>> while using bifurcan, then the bifurcan types need to have the Clojure >>>>>> wrapper. The alternative appears to be re-implementing at least a large >>>>>> subset of collection-related spec code, which is a lot to bite off. Also >>>>>> tried updating some existing code to use bifurcan. Similar to spec, >>>>>> there >>>>>> are going to be cases which are less perf sensitive, where it would be >>>>>> nice >>>>>> to use code that is polymorphic for collections, and drop down to the >>>>>> fast >>>>>> interface in perf-sensitive parts. >>>>>> >>>>>> >>>>>> On Monday, April 17, 2017 at 1:52:39 PM UTC-7, Dave Dixon wrote: >>>>>>> >>>>>>> What is the issue with wrapping in Clojure interfaces? Added >>>>>>> overhead of function calls? >>>>>>> >>>>>>> I'm finding myself in the process of doing some of this, at least >>>>>>> for constructors. Also thinking of generating predicates/generators for >>>>>>> use >>>>>>> with spec. >>>>>>> >>>>>>> On Monday, March 27, 2017 at 9:51:46 AM UTC-7, Zach Tellman wrote: >>>>>>> >>>>>>>> This is a slightly irregular announcement, because it's not for a >>>>>>>> Clojure library. Rather, it's for a library written purely in Java: >>>>>>>> https://github.com/lacuna/bifurcan. >>>>>>>> >>>>>>>> This is a collection of mutable and immutable data structures, >>>>>>>> designed to address some of my personal frustrations with what's >>>>>>>> available >>>>>>>> in the Clojure and Java ecosystems. Notably, they have pluggable >>>>>>>> equality >>>>>>>> semantics, so while they *can* use Clojure's expensive hash and >>>>>>>> equality >>>>>>>> checks, they don't *have* to. They also provide high-performance >>>>>>>> mutable >>>>>>>> variants of the data structure which share an API with their immutable >>>>>>>> cousins. >>>>>>>> >>>>>>>> I'm posting it here to ask for people's thoughts on how, if at all, >>>>>>>> this should be exposed as a Clojure library. It would be simple to >>>>>>>> simply >>>>>>>> wrap them in the Clojure interfaces and make them behave identically >>>>>>>> to >>>>>>>> Clojure's own data structures, but that kind of obviates the point. >>>>>>>> However, creating an entirely new set of accessors means that we can't >>>>>>>> leverage Clojure's standard library. >>>>>>>> >>>>>>>> It's possible that I'm alone in my frustrations, and no Clojure >>>>>>>> wrapper is necessary. But if this does solve a problem you have, I'd >>>>>>>> like >>>>>>>> to hear more about what it is, and how you think Bifurcan might help. >>>>>>>> Please feel free to reply here, or to grab me at Clojure/West and talk >>>>>>>> about it there. >>>>>>>> >>>>>>>> Thanks in advance, >>>>>>>> Zach >>>>>>>> >>>>>>> -- >>>>>> 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 a topic in >>>>>> the Google Groups "Clojure" group. >>>>>> To unsubscribe from this topic, visit >>>>>> https://groups.google.com/d/topic/clojure/1m_I7IrDGb0/unsubscribe. >>>>>> >>>>> To unsubscribe from this group and all its topics, 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 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 a topic in the >>>> Google Groups "Clojure" group. >>>> To unsubscribe from this topic, visit >>>> https://groups.google.com/d/topic/clojure/1m_I7IrDGb0/unsubscribe. >>>> To unsubscribe from this group and all its topics, 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 clo...@googlegroups.com >> <javascript:> >> 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 <javascript:> >> For more options, visit this group at >> http://groups.google.com/group/clojure?hl=en >> --- >> You received this message because you are subscribed to a topic in the >> Google Groups "Clojure" group. >> To unsubscribe from this topic, visit >> https://groups.google.com/d/topic/clojure/1m_I7IrDGb0/unsubscribe. >> To unsubscribe from this group and all its topics, send an email to >> clojure+u...@googlegroups.com <javascript:>. >> 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.
