5 ms·

That's the idea of Clojure's persistent data structures. Values share the parts of themselves which haven't changed, so they are not copied. "All of the Clojur

• fauigerzigerk 17y ago
  I know. I read Stu Halloway's book and I read some articles about how the persistent data structures work. But I also did some tests myself. Performance isn't great but that's not so much the issue for me. Memory use is a problem though. I can't have a list of a million integer pairs take 160MB of RAM.
  • jefffoster 17y ago
    There was some work recently to improve the performance of persistent data structures. See http://clojure.org/transients http://clojure.org/transients Calling (transient x) gives you a mutable copy of x which is created in O(1) time. You can then use functions like conj! and assoc! to modify the data structure in place. When you've finished, call (persistent! x) which returns you to a pure data structure (another O(1) operation).
    • fauigerzigerk 17y ago
      Ok, but that has nothing to do with memory usage, which is my problem with clojure.
  • jrockway 17y ago
    I can't have a list of a million integer pairs take 160MB of RAM. This doesn't have much to do with sharing. Rather, it is the overhead of boxing the integers. If you want a byte array that you'll interpret as an array of machine integers (as an int * would be in C), then you need to use that type instead of a "list of integers" that your language provides. That "list of integers" is optimized for something other than space (integer math not overflowing, O(1) insertions, etc.). Conversely, arrays of machine ints have many annoying quirks, but the underlying hardware can process them really quickly, and they are very frugal with respect to memory use. (No overhead, basically.) As it stands now, most language implementations are not smart enough to see that you just used lists because you like the syntax, but meant to use byte arrays. (Or, you used Integers instead of ints.) Tracemonkey, GHC, and probably other languages have code to help optimize this case. dons wrote a nice article about how GHC's codegen produces code that uses unboxed types even though the programmer used boxed types. As far as I know, Clojure is not really smart enough to optimize much right now (beyond the JIT that the JVM does), so this is probably a problem. The solution is to fix Clojure or to use the native types. I don't know how to do this, as I don't use Java or Clojure, but it sounds like a Simple Matter Of Programming to expose a shared array of unboxed integers. (There are a lot of papers on this.) Functional programming is a "new idea" in terms of people using it for "Real Work", so there is a long way to go in terms of writing excellent optimizing compilers. It is getting better very quickly, though.
    • fauigerzigerk 17y ago
      Well, I have played around with this for some time and I found that boxing is just one reason. Another one is that clojure structs seem to always act as generic maps even if only predefined elements are actually stored. This seems like an easy one to optimize. But if I put lots of structs in a Java ArrayList, memory use goes down significantly, so clojure vectors are much less efficient regardless of boxing.
      • pmjordan 17y ago
        Have you poked around the (Java) source for clojure's data structures? It's very readable, and if you have any ideas for improving their memory footprint, I think a lot of people (including myself) would appreciate hearing about them.