Re: [ANN and RFC] Bifurcan: impure functional data strucures

[Zach Tellman]

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

Re: [ANN and RFC] Bifurcan: impure functional data strucures

[Dave Dixon]

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