Worth noting, GraalVM's JVM implementation has a different JIT compiler which seems to give better performance for highly dynamic and polymorphic languages like Clojure and Scala
I don't think there's an immediately available answer here. The wide branch factor in Clojure's implementation is very iteration-friendly, less so for updates.
Worth checking out are BTrees and Hitchhiker trees, but I think a definitive answer will be implementation dependent even in those cases, i.e. one might win out over the other for a specific branch factor or other tune-able parameters
That's a fair criticism, but indulge this hypothetical, if you will:
- assume the sliding window transducer existed in the standard library (there's an open jira for it)
- assume the programmer is not an expert, but is familiar with stuff like boxed maths in Clojure, which isn't hard to work around, well documented [1], and has a known performance impact
- assume the programmer will avoid using `last`
- assume the programmer is comfortable using transducers
In short, that the transducer exists and the programmer has at least 6 months of experience programming in Clojure full time.
Will you consider the resulting implementation complicated, in depth or non idiomatic? There's always the possibility I'm just used to it so it comes naturally to me, but as the title suggests, I consider the result, before dropping down to arrays, way more idiomatic than the initial implementation.
I don't begrudge CL's speed and implementation, it's the readiness with which Clojure is dismissed as being slow with only surface familiarity with it.
> although he doesn't really explain why HAMTs specifically are slow
Hello, author here :)
HAMTs are certainly slower, for "churning" operations, i.e., lots of updates, which is where Clojure exposes the transient API, which gives you limited localized mutability (some terms and conditions may apply)
Where iteration is concerned, they standard library implementation is pretty good. It relies on chunks of 64 element arrays which store the keys and values contiguously. Thus, APIs which expose direct iteration, Iterator and IReduce(Init) operate on these chunks one at a time. It isn't as fast as primitive arrays, but it's pretty fast.
Others have made similar comments on comparing apples to oranges when comparing optimized CL to idiomatic Clojure, but what they didn't address was "idiomatic Clojure".
Threading a sequence through a bunch of lazy operations is good for development time, but at this point I wouldn't consider it idiomatic for "production" code.
Two things in the implementation are performance killers:
Laziness and boxed maths.
- baseline: Taking your original implementation and running it on a sequence or 1e6 elements I generated, I start off at 1.2 seconds.
- Naive transducer: Needs a transducer of a sliding window which doesn't exist in the core yet[0], 470ms
- Throw away function composition, use peek and nth to access the vector: 54ms
- Map & filter -> keep: 49ms
- Vectors -> arrays: 29ms
I'd argue only the last step makes the code slightly less idiomatic. Might even say that aggressively using juxt, partial and apply is less idiomatic than simple lambdas
https://github.com/edn-format/edn