Re: [Bug-apl] Optimizations revived

[Juergen Sauermann]

Hi Blake, I am afraid that the matter is not that simple. For example if you pass a value (-pointer) from one C++ function to another as function argument, would that be a new owner? If yes then we would get very many list insertions and deletions. If no then a number of functions that return their argument, but only under certain conditions, would need to be rewritten. Another problem is nested arrays (currently the nested value does not know the value that contains it). The main cases of cloning appear when assigning and referencing variables. We have seen examples in the past where optimizing one or the other has produced incorrect results (David's ⍬ problem and my recent A+ (A[3]←3) ⊢ A←10⍴10 example). And we have only opinions and no hard numbers that tell us how many cycles the cloning really cost use. It is pretty easy to construct an example demonstrating that this number is huge. But it is equally easy to  produce a counter-example showing that a (doubly-) linked list approach is slower than the present scheme. My approach would be to add some performance counters to really understand this better. /// Jürgen On 08/24/2014 11:35 PM, blake1...@gmail.com wrote: What about keeping a linked list of owners, figure who is getting written to, and clone that one only?  Typically there would only be one owner, and you can do the linked check with inline code.. I think avoiding a lot of cloning is important. Blake -- Sent from my HP TouchPad On Aug 24, 2014 10:01 AM, Elias Mårtenson <loke...@gmail.com> wrote: Of course, there are definitely times where cloning is necessary. The typical example would of course be when a value is assigned to another and that value is subsequently changed (by using indexed assignment). And you mentioning the issue of not know who are the owners of an object reminds me of the fact that I also came across that issue. At first I was thinking that the problem is trivial; that you simply clone if the owner count is >1. Then I realised that there could be many owners, but those owners are not going to touch the object anymore. There must be an optimal solution here. I'm sure you agree with me about the ideal situation: Where there is no cloning except for when it's needed because an object will be changed. Now: Can you confirm if I'm correct in my assessment that the only thing that forces cloning in the first place is indexed assignment? If APL had no such feature, then there would be zero need for cloning, yes? Regards, Elias On 24 August 2014 22:46, Juergen Sauermann <juergen.sauerm...@t-online.de> wrote: Hi Elias, I don't know. Actually I just found a nasty example which renders my statement below ("I believe the clone() call in Symbol::resolve() can be skipped completely") wrong:       A←10⍴10       A+ (A[3]←3) ⊢ A Currently a value is cloned when it is assigned to a variable and again when the variable is referenced. The above example shows why cloning on reference is needed. You get the correct 20 20 13 20 20 20 20 20 20 20 when you clone and the wrong 20 20 6 20 20 20 20 20 20 20 if not. The problem that I see with CoW is that we know how many owners a value has but not who they are. And you definitely dont want to clone on indexed assignment because very often you have a large value and only a small part being updated. With CoW you dont want to clone the value that is being assigned but rather the other (possibly many copies) and those we don't know. I also don't share your opinion that the cloning is unnecessary. I think it is more so that it is sometimes unnecessary, but at the time when you would not  clone you don't have enough information to properly make that decision. /// Jürgen On 08/24/2014 04:04 PM, Elias Mårtenson wrote: Thanks for the explanation. With this in mind, I'm wondering about two specific cases and how you intend to solve them (these are are ones that gave me the biggest headache): First of all, how will you avoid doing a clone() on every update using indexed assignment? You need some way to know whether or not an instance have to be cloned or can be modified in-place. A related case is normal left-arrow assignment. It is not desirable to do a clone() on every assignment either. You want to basically do a "deferred clone" (i.e. CoW) so that the instances can be shared in both variables until one of them is updated. When I was thinking about this, I couldn't get away from concluding that a full CoW implementation is needed in order to avoid all unnecessary cloning. Regards, Elias On 24 August 2014 00:01, Juergen Sauermann <juergen.sauerm...@t-online.de> wrote: Hi Elias, normally APL values are not written to. The exception is indexed assignment. I believe the clone() call in Symbol::resolve() can be skipped completely. This is probably the most frequently used clone() case. I suppose copy-on-write semantics is achieved when all clone() calls are gone. Many of the remaining clone() calls are specific to certain functions so their performance impact should be small. I haven't done the above before the 1.4 release because I didn't want to release a not-so-well tested optimization. /// Jürgen On 08/23/2014 05:32 PM, Elias Mårtenson wrote: Cool :-) Speaking of this, I did spend quite a bit of time some time ago to try to figure out an easy way to get generic copy-on-write semantics, but I never came to a satisfactory conclusion. I might revisit it later. Have you thought about it? It is, after all, related to this specific optimisation. Regards, Elias On 23 August 2014 23:29, Juergen Sauermann <juergen.sauerm...@t-online.de> wrote: Hi, I have revived Elias' in-place optimization for A⍴B and ,B now usinng a different way of figuring if B is in use. SVN 445. /// Jürgen