Re: update in place for unique references
Most structures of this type would start life as a uniquely-referenced structure (either empty or a copy of an immutable), and have lots of mutations effectively applied to them in a safe environment, until they are ready to be frozen and released to the world as an immutable version of the structure. It is possible to achieve this behavior explicitly if you really wanted to: (defn create-add-2 [] (with-local-vars [x 1] (do (var-set x 1) (var-set x (inc @x)) (let [z @x] (fn [y] (+ y z)) (Some structures would stay uniquely-referenced their whole life - used for performance in some single-threaded encapsulated mutation-based algorithm.) Such an aggressive optimizer might be unhappy with a runtime check and opt for an unsafe mutable: user= (def p (java.awt.Point. 0 0)) #'user/p user= p #Point java.awt.Point[x=0,y=0] user= (.setLocation p 1 2) nil user= p #Point java.awt.Point[x=1,y=2] But might still be unhappy with having to use object calls, at which point I don't think Clojure is the right language. However lucky for them they could still go away and implement an incredibly efficient java api and call it from within Clojure very easily. They would still want to wring the last few drops of performance and write it in C. Actually they could still invoke that code at a high level via JNI but of course would want to keep the calls to a minimum to avoid calling overhead. I should also clarify one point. I am not asking for this language feature so much as asking whether people have thought about it. There may (or may not) be good reasons for not offering such a language feature. I'm just wondering if it has been considered. (And trying to get a feel for the strengths and weaknesses of Clojure - I am very new to it.) I'm just an observer, but if I can't see such a feature appealing to the performance user because it wont ever be as fast as they want it to be. To appeal to the general user transparent implementation, which it can't be if you want to preserve all the features. A subset between these exist, but is quite small and not a far step from moving up or down. * uniquely-referenced (arbitrary mutation changes effectively allowed, but only ever referred to uniquely (runtime enforced)). I think that pretty accurately describes C++, its not fun debugging a runtime enforced coredump full of crap. :) I know that's not what your proposing sorry but I couldn't resist the analogy! I'm not saying its a bad idea, I just don't find it compelling to me personally. Regards, Tim. --~--~-~--~~~---~--~~ 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 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 -~--~~~~--~~--~--~---
Re: update in place for unique references
On Jan 8, 10:45 pm, Mark P pierh...@gmail.com wrote: I should also clarify one point. I am not asking for this language feature so much as asking whether people have thought about it. There may (or may not) be good reasons for not offering such a language feature. I'm just wondering if it has been considered. (And trying to get a feel for the strengths and weaknesses of Clojure - I am very new to it.) I think the big strength of Clojure is how easy it is to integrate Java code. If you have some performance-critical code you can always drop down to Java. Certainly, performance is important to Clojure, but I think the assumption is that it will never compete with pure Java on speed. -Stuart Sierra --~--~-~--~~~---~--~~ 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 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 -~--~~~~--~~--~--~---
Re: update in place for unique references
Hi Tim, I appreciate your comments. It is possible to achieve this behavior explicitly if you really wanted to: (defn create-add-2 [] (with-local-vars [x 1] (do (var-set x 1) (var-set x (inc @x)) (let [z @x] (fn [y] (+ y z)) That's true. Only the (inc @x) isn't update-in-place. Presumably some java something could be used here instead to get true update in place. Such an aggressive optimizer might be unhappy with a runtime check and opt for an unsafe mutable: user= (def p (java.awt.Point. 0 0)) #'user/p user= p #Point java.awt.Point[x=0,y=0] user= (.setLocation p 1 2) nil user= p #Point java.awt.Point[x=1,y=2] But might still be unhappy with having to use object calls, at which point I don't think Clojure is the right language. However lucky for them they could still go away and implement an incredibly efficient java api and call it from within Clojure very easily. They would still want to wring the last few drops of performance and write it in C. Actually they could still invoke that code at a high level via JNI but of course would want to keep the calls to a minimum to avoid calling overhead. What you're saying could well be true. Ie a runtime check of unique reference might not be acceptable where performance is a major concern. But there are two ways around this. 1. Have the ability to turn runtime uniqueness checking on or off. This way code can be tested with the check on, but then run with it off once we are convinced the code is correct (at coder's own risk of course). 2. Take up Mark Fredrickson's suggestion of a code walking analysis macro to prove uniqueness before running the code. That way no runtime check is needed. The fact that java method calls are always expensive is still a problem though. As you say, ultimately a call to a C or C++ routine via JNI might be the only real performance answer. I wish there were a better way. I'm just an observer, but if I can't see such a feature appealing to the performance user because it wont ever be as fast as they want it to be. To appeal to the general user transparent implementation, which it can't be if you want to preserve all the features. A subset between these exist, but is quite small and not a far step from moving up or down. You might be right here, though I still feel uniqueness is a good tool for writing safe and somewhat transparent equivalent to mutation based code. C++ is (unfortunately) my current main language and I use a runtime uniqueness framework to ensure much more reliable mutation based code there. But I think Java's insistence on virtual function calls may make a highly efficient uniqueness approach difficult to achieve in Clojure. * uniquely-referenced (arbitrary mutation changes effectively allowed, but only ever referred to uniquely (runtime enforced)). I think that pretty accurately describes C++, its not fun debugging a runtime enforced coredump full of crap. :) I know that's not what your proposing sorry but I couldn't resist the analogy! I'm not saying its a bad idea, I just don't find it compelling to me personally. But adhering to a uniqueness discipline within C++, together with a functional approach like FC++, does lead to more reliable and more transparent (and somewhat efficient) C++ code. And uniqueness in a lisp language should be much more elegant than my C++ implementation. But I think you and Mark Fredrickson are right to point out that limitations within the JVM itself may make efficiency via uniqueness that is competative with C/C++, impossible to achieve. I'm still hopeful there may be a way, but I can't see it just now. Cheers, Mark P. --~--~-~--~~~---~--~~ 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 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 -~--~~~~--~~--~--~---
Re: update in place for unique references
Clean doesn't allow mutation, so it has to do tricks like this or else you'd never be able to write a useful program. Clojure gives you a set of data structures that do very fast non-destructive update. Clojure also gives you tools like atoms, refs, and full access to Java's mutable behavior to specify update in place if that's what you want. Since Clojure gives you a full range of immutable/mutable update choices, I fail to see how Clean's uniqueness typing is at all relevant to Clojure. --~--~-~--~~~---~--~~ 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 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 -~--~~~~--~~--~--~---
Re: update in place for unique references
Clojure gives you a set of data structures that do very fast non-destructive update. Clojure also gives you tools like atoms, refs, and full access to Java's mutable behavior to specify update in place if that's what you want. Yes, I can see that one could implement this oneself via Java. But it wouldn't be an official part of the language. What I am wondering is whether update-in-place for unique references could lead to greater efficiencies (in some cases) than Clojure's current non-destructive updates. And without harming referential transparency or concurrency benefits. Fundamentally I would have thought update-in-place beats update-by-replace in both execution speed and in memory usage. The only problem with it is that it usually breaks referential transparency as well as causing problems with concurrency. But in the case of a unique reference that is about to disappear, update-in-place does no harm! The memory is about to become obsolete soon anyway so why not commandeer it? And if commandeered, why not update it in place - as nothing else is looking at it. I realize there are issues, but maybe these could be solved and it could lead to even more efficient (both time and memory) code from Clojure, while not sacrificing its strengths. I'm just wondering whether anyone has thought about it. And if so, whether it has potential, or whether there are good reasons why it is not practical. Cheers, Mark P. --~--~-~--~~~---~--~~ 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 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 -~--~~~~--~~--~--~---
Re: update in place for unique references
Hi Mark F, Thanks for your responses. 1. Data: Is this really a problem that is slowing down Clojure programs in practice? Can you provide some data to that effect? I would suggest writing a couple of Java benchmarks - one that updates a simple structure in place and one that only creates new data. Time them. Write more benchmarks, but this time do it in Clojure (though perhaps with some straight Java calls to make the updates). Are there differences in the Java versions from the Clojure versions? Are there differences in the update vs new data versions? Writing some test code is not a bad idea, but from what I heard Rich Hickey say in his online talks, probably unnecessary to establish that using Clojure built-in data structures involves a performance hit (in the single-thread case anyway). I got the impression that Clojure structures are somewhere in the range of 1.5 to 4 times worse than mutation based structures. Of course, this performance is quite an achievement, given the advantages of Clojure's approach. But for applications which are performance critical, I am wondering whether a uniqueness-based update-in-place would offer a complementary well performing alternative. 2. Take a page from the Scheme playbook. Don't ask the language to implement this feature, ask for the minimal set of tools that you need to implement it. I would think a code walking escape analysis macro could be very useful. Instead of run-time reference counting, the macro could find data that is guaranteed not to escape its scope via a closure (e.g. let bound locals that are not used in any (fn [] ...)s ). What would you need access to? Additional JVM byte-code instructions? Post-compile processing by user code? Update in place methods for the normally immutable types? I don't know exactly what you'd need, but ask for that before asking for a much bigger feature. The escape analysis macro sounds interesting. But an initial approach might be, for each of these new data structures (mutation based under the hood) to have two versions of each structure: * immutable (ie no more changes will ever occur - if you want a modification you will have to make a full copy); and * uniquely-referenced (arbitrary mutation changes effectively allowed, but only ever referred to uniquely (runtime enforced)). Most structures of this type would start life as a uniquely-referenced structure (either empty or a copy of an immutable), and have lots of mutations effectively applied to them in a safe environment, until they are ready to be frozen and released to the world as an immutable version of the structure. (Some structures would stay uniquely-referenced their whole life - used for performance in some single-threaded encapsulated mutation-based algorithm.) I should also clarify one point. I am not asking for this language feature so much as asking whether people have thought about it. There may (or may not) be good reasons for not offering such a language feature. I'm just wondering if it has been considered. (And trying to get a feel for the strengths and weaknesses of Clojure - I am very new to it.) 3. Remember that Clojure relies on the JVM for its allocation and GC. Clojure is not issuing malloc and free calls. The JVM will not make it easy to repurpose the storage of one object with a new object, without going through a method. Maybe the way to handle this (at least initially) would be to only provide uniqueness interfaces to some of Java's main structures. Perhaps not as general as would be ideal, but would easily allow repurposing via a method. Thanks again for your input. Cheers, Mark P. --~--~-~--~~~---~--~~ 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 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 -~--~~~~--~~--~--~---
update in place for unique references
I am new to clojure, but it seems very interesting. Has anyone thought about allowing update in place for situations where it is safe? Suppose you have (def y (tripleit x)) and you know that there is only a single reference to x at this point, then it would be safe to implement it as y takes on the storage of x and this is multiplied by 3 in-place. Well, I should say it's safe as long as x loses scope at this point. The fact that y has gained its storage and done an update in place shouldn't bother anyone or cause any loss in purity. This is what uniqueness types are used for in the Clean functional lanugage. (And logic language Mercury uses unique modes.) Now I realize there is the question in Clojure of how do we know whether it's unique. Clean does it via the type system. But one could have other mechanisms for ensuring uniqueness. One would be to keep a runtime track of references and only allow an update-in-place primitive in the case of a single reference. If this were attempted when multiple references existed, a runtime error would occur. Has anyone thought about this kind of update-in-place methodology? It seems to be one of the reasons why both Clean and Mercury achieve good performance. Perhaps there are good reasons why this approach is not workable in clojure (or not useful), but I'd be interested to hear why. Thanks, Mark. --~--~-~--~~~---~--~~ 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 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 -~--~~~~--~~--~--~---