valueDiff for arrays?

[Mark Waddingham]

On 2018-08-04 18:37, Brian Milby via use-livecode wrote:
> @Mark,
> I wasn't necessarily suggesting that it belonged in the engine, but
> pointing out why I would look at the code.

:)

Understanding how the engine actually operates is important, because it 
can help to design the LCS implementation to work with its 
implementation rather than against it.

> I will say from some other things that I've looked at recently that 
> speed
> would be so much faster in the engine - if it was a feature that 
> merited
> being there.  I did kind of cheat in that I looked at how the engine 
> did
> the array union/intersect functions.  The source actually contains LCS
> versions of the logic too.  What I'm thinking is that there will be an
> array size where iterating the array 3 times (twice by the engine-
> intersect and symmetric difference or union) will be faster than 
> iterating
> the array once in LCS (using modified union logic).

Yes - which is why digging into the engine code and experimenting to 
produce a good higher-level LCS implementation is the right approach.

Adding variant codepaths based on size of arrays and such is probably 
inappropriate in the engine - because it will likely always be dependent 
on the data set. (If you can prove that it is independent of dataset - 
or is almost always what you might say is the amortized best-case - like 
qsort - which is actually O(n^2) worst case, its just that you have to 
work pretty darn hard to produce its worst-case behavior - then it makes 
sense to do so).

Sometimes optimizations will be independent of all of that though. For 
example:

All array operations are currently X, Y -> Z - i.e. not in-place. In the 
cases where (for example):

   intersect X with Y

Is operating on an X which can safely be mutated directly - there is a 
much more efficient implementation which does not require creating a new 
array (i.e. you just loop through and delete the keys in X which aren't 
in Y).

The reason the current implementations are in-place is actually due to 
the syntax dispatch - that needs to be able to detect the 'correct' 
situation where in-place can be used and then use it.

> All of the current engine array code is based on comparing the key.  
> The
> distinction here is that a value comparison is also required.

Indeed - which is why I wonder whether there are more fundamental 
operations which do a basic 'key-ish' thing which would be appropriate 
for being in the engine - as then any variation on what 'valueDiff' 
might mean could be coded in LCS with little overhead compared to a 
hard-coded C++ version.

i.e. I can certainly say that a patch which makes in-place array 
operations work (in a way which doesn't cause a ripple effect elsewhere 
in terms of locality and such) would be accepted.

I can also certainly forsee there being a variation on the 
union/intersect etc. commands which are 'general' operations taking into 
the key that would also make sense to be in the engine... However, I'm 
not sure quite what that/they would be - but would be most interested to 
see proposals / examples of (and implementations too) :)

So in no way was I intending to discourage you from your efforts - just 
trying to focus on trying to find where the line is between engine/LCS 
in terms of interface - that's the hardest part. At the end of the day, 
the actual coding in one language or another when you know what you are 
meaning to achieve is (communally) quite trivial.

Warmest Regards,

Mark.

-- 
Mark Waddingham ~ mark at livecode.com ~ http://www.livecode.com/
LiveCode: Everyone can create apps