Fwd: Speed of control lookup (Was Re: Parent of Target)

classic Classic list List threaded Threaded
8 messages Options
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Fwd: Speed of control lookup (Was Re: Parent of Target)

** Clarence P Martin ** via use-livecode
On 2017-08-11 11:12, Mark Waddingham via use-livecode wrote:
> On 2017-08-10 21:10, Richard Gaskin via use-livecode wrote:
>> How might I measure the benefits of long ID caching?

Here is perhaps a better set of simple benchmarks to compare approaches
to lookup (related to ids, anyway):

========

on mouseUp
    local tIterations
    put 100000 into tIterations

    -- card id is 1002
    -- button id is 1003
    -- group id is 1004
    local tLongId
    put the long id of button id 1003 of group id 1004 of card id 1002
into tLongId

    local tButtonIdOfStack
    put "button id 1003 of stack" && quote & "LongIdSpeedTest" & quote
into tButtonIdOfStack

    local tButtonIdOfCardIdOfStack
    put "button id 1003 of card id 1002 of stack" && quote &
"LongIdSpeedTest" & quote into tButtonIdOfCardIdOfStack

    local tTime
    put the millisecs into tTime
    repeat tIterations times
       get the id of me
    end repeat
    put "Control" && (the millisecs - tTime) & return into msg

    put the millisecs into tTime
    repeat tIterations times
       get the id of tLongId
    end repeat
    put "GetIdOfLongIdInString" && (the millisecs - tTime) & return after
msg

    put the millisecs into tTime
    repeat tIterations times
       get the id of tButtonIdOfCardIdOfStack
    end repeat
    put "GetIdOfButtonIdOfCardIdOfStackInString" && (the millisecs -
tTime) & return after msg

    put the millisecs into tTime
    repeat tIterations times
       get the id of tButtonIdOfStack
    end repeat
    put "GetIdOfButtonIdOfStackInString" && (the millisecs - tTime) &
return after msg

    put the millisecs into tTime
    repeat tIterations times
       get the id of button id 1003 of group id 1004 of card id 1002 of
stack "LongIdSpeedTest"
    end repeat
    put "GetIdOfButtonIdOfGroupIdOfCardIdOfStack" && (the millisecs -
tTime) & return after msg

    put the millisecs into tTime
    repeat tIterations times
       get the id of button id 1003 of card id 1002 of stack
"LongIdSpeedTest"
    end repeat
    put "GetIdOfButtonIdOfCardIdOfStack" && (the millisecs - tTime) &
return after msg

    local tStackString
    put "LongIdSpeed" & "Test" into tStackString

    put the millisecs into tTime
    repeat tIterations times
       get the id of button id 1003 of group id 1004 of card id 1002 of
stack tStackString
    end repeat
    put "GetIdOfButtonIdOfGroupIdOfStackNotName" && (the millisecs -
tTime) & return after msg

    put the millisecs into tTime
    repeat tIterations times
       get the id of button id 1003 of card id 1002 of stack tStackString
    end repeat
    put "GetIdOfButtonIdOfCardIdOfStackNotName" && (the millisecs -
tTime) & return after msg
end mouseUp

========

On my machine (in 8.1.5) I get:

Control 21
GetIdOfLongIdInString 714
GetIdOfButtonIdOfCardIdOfStackInString 497
GetIdOfButtonIdOfStackInString 320
GetIdOfButtonIdOfGroupIdOfCardIdOfStack 56
GetIdOfButtonIdOfCardIdOfStack 53
GetIdOfButtonIdOfGroupIdOfStackNotName 65
GetIdOfButtonIdOfCardIdOfStackNotName 63

So, currently, there is a significant overhead to getting a control
reference out of a string - the minimum you actually need in a string to
uniquely identify a control (which may or may not have per-card data) is
"control id ... of card id ... of stack ...".

Indeed - using the minimal info you need hard-coded in syntax:

       get the id of button id 1003 of card id 1002 of stack tStackString

Is about 10 times faster than using a long id in a string and about 8
times faster than using a modified form of a string id to cut out the
(strictly) unnecessary bits:

       get the id of "button id 1003 of card id 1002 of stack
LongIdSpeedTest" -- quoted name, appropriately

So, my advice changes *slightly* - if you are doing tight loops which
need to manipulate lots of controls in the current card of the
defaultStack use:

       control id <id>

If the things aren't on the current card of the default stack, then
extract the card id and stack name outside of the loop and use:

       control id <id> of card id tCardId of stack tStackName

The question of course is 'how fast could we get long id parsing to be'
(as that is the bottleneck here, or at least appears to be).

Warmest Regards,

Mark.

P.S. Due to a mailing server glitch any mails which were sent here
between 12:30BST and 14:00BST will not have got through.

--
Mark Waddingham ~ [hidden email] ~ http://www.livecode.com/
LiveCode: Everyone can create apps

_______________________________________________
use-livecode mailing list
[hidden email]
Please visit this url to subscribe, unsubscribe and manage your subscription preferences:
http://lists.runrev.com/mailman/listinfo/use-livecode
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Fwd: Speed of control lookup (Was Re: Parent of Target)

** Clarence P Martin ** via use-livecode
On 2017-08-11 14:57, Mark Waddingham via use-livecode wrote:
> The question of course is 'how fast could we get long id parsing to
> be' (as that is the bottleneck here, or at least appears to be).

Okay so I got stuck on what I am *meant* to be doing, so spent a little
time trying to answer this question.

The results are quite encouraging...

So, my idea was this - long ids which the engine generates have a *very*
strict structure - so write a very fast parser for them which fails as
soon as it encounters anything it doesn't expect. If this happens you
just use the existing (relatively slow) method which handles all the
edge cases.

It turns out you can hand-craft a parser for 'the long id' in about 150
lines of C (char-bashing, one might call it, as opposed to bit-bashing)
and assuming you restrict yourself to only looking up things on the
current card of the target stack, and don't check group ownership
(oops!) you end up with something which can resolve a long id in about
the same time as you could if you hand-coded the syntax. i.e.

   put "button id 1003 of group id 1004 of card id 1002 of stack " &
quote & "MyStackName" & quote into tRuggedId
   get the id of tRuggedId

   -- has about the same speed (assuming all those objects are in the
cache) as

   put the id of button id 1003 of group id 1004 of card id 1002 of stack
"MyStackName"

Now, I do wonder if the long id parsing method we currently have is
actually using the stack-id cache everywhere it could (this code is
somewhat old and knotty - so it is quite hard to see) - so I'm not sure
quite how fair the above comparison is with current long id parsing
(were the latter as optimal as it potentially could be) but there is
obviously quite a significant overhead in the way chunks are parsed from
strings (which I kind of already knew - but perhaps not just *how
much*!).

Anyway, it is quite pleasing to know that we perhaps don't need the
complexity of 'caching an object-handle along side a string from which a
long id has been parsed' (where getting the cache validation right is
going to be hard to do performantly enough) as we can probably make
parsing of long ids (or variants of) themselves so quick, that the time
taken to do so is thoroughly lost in the actual operation they are being
used for.

This was just an 'experiment', so I can't really say when this change
might (if ever) appear - however, it certainly suggests a slightly less
fiddly approach than the caching method.

It has also suggested (to me, at least) a slightly different approach -
we make the return value of the 'long id' property of objects what you
might call a StringyLongId value. Instead of returning a string:

   button id 1003 of group id 1004 of card id 1002 of stack "MyStackName"

It would be a value which acts like a string, but internally stores:

     [ BUTTON, 1003, [ 1004 ], 1002, "MyStackName" ]

i.e. A list of component parts - [ main chunk, main chunk id, [ group
id, ... ], card id, stack name/filename ]

This has the advantage that you use up a great deal less memory for long
ids of very frequently referenced objects (filenames / names can be
quite long!). They can be resolved quickly assuming the stack-id cache
(and if we add a name / filename cache for top-level stacks); compared
more quickly; and still be rendered as a string when doing stringy
things to them (it would also be possible to optimize the 'word' chunk
for them).

This has the *distinct* advantage of not needing to be validated (long
ids change as objects move around in the hierarchy or id / names change
] before use.

Of course, this actually requires a bit of machinery we don't actually
have (but could be used for other things) - the ability for a value
(internally) to be able to act like a string, but not actually be a
string.

On balance the optimized long id chunk parser is probably less work (as
it only needs a bit of code in *one* place - in the chunk evaluator);
and probably less prone to causing regressions - especially if we only
used the optimized code path in cases where we were sure there weren't
any 'difficult' edge-cases to deal with.

I suppose I should now get back to what I was meant to be doing...

Warmest Regards,

Mark.

--
Mark Waddingham ~ [hidden email] ~ http://www.livecode.com/
LiveCode: Everyone can create apps

_______________________________________________
use-livecode mailing list
[hidden email]
Please visit this url to subscribe, unsubscribe and manage your subscription preferences:
http://lists.runrev.com/mailman/listinfo/use-livecode
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Speed of control lookup (Was Re: Parent of Target)

** Clarence P Martin ** via use-livecode

> On 12 Aug 2017, at 1:23 am, Mark Waddingham via use-livecode <[hidden email]> wrote:
>
> It has also suggested (to me, at least) a slightly different approach - we make the return value of the 'long id' property of objects what you might call a StringyLongId value. Instead of returning a string:
>
>  button id 1003 of group id 1004 of card id 1002 of stack "MyStackName"
>
> It would be a value which acts like a string, but internally stores:
>
>    [ BUTTON, 1003, [ 1004 ], 1002, "MyStackName" ]

Hmm… Would it be a good idea to create a new ID form with the bare minimum to identify an object. Say:

<type> id <id> of card id <id> of stack “<stack name>”

Although I guess unplaced groups would need just <type> id <id> of stack “<stack name>”

That would mean speed improvements could be done on an object reference that is relatively robust to changes in the object tree and unless you are creating an IDE you would be very unlikely to need to do the LCB object reference repository thing.

Cheers

Monte
_______________________________________________
use-livecode mailing list
[hidden email]
Please visit this url to subscribe, unsubscribe and manage your subscription preferences:
http://lists.runrev.com/mailman/listinfo/use-livecode
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Speed of control lookup (Was Re: Parent of Target)

** Clarence P Martin ** via use-livecode
On 08/11/2017 02:58 PM, Monte Goulding via use-livecode wrote:

> Hmm… Would it be a good idea to create a new ID form with the bare minimum to identify an object.

<cough>
UUID
</cough>

--
  Mark Wieder
  [hidden email]


_______________________________________________
use-livecode mailing list
[hidden email]
Please visit this url to subscribe, unsubscribe and manage your subscription preferences:
http://lists.runrev.com/mailman/listinfo/use-livecode
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Speed of control lookup (Was Re: Parent of Target)

** Clarence P Martin ** via use-livecode

> On 12 Aug 2017, at 8:11 am, Mark Wieder via use-livecode <[hidden email]> wrote:
>
>> Hmm… Would it be a good idea to create a new ID form with the bare minimum to identify an object.
>
> <cough>
> UUID
> </cough>

Let’s not start that again ;-)
_______________________________________________
use-livecode mailing list
[hidden email]
Please visit this url to subscribe, unsubscribe and manage your subscription preferences:
http://lists.runrev.com/mailman/listinfo/use-livecode
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Speed of control lookup (Was Re: Parent of Target)

** Clarence P Martin ** via use-livecode
In reply to this post by ** Clarence P Martin ** via use-livecode
On 2017-08-11 23:58, Monte Goulding via use-livecode wrote:
> That would mean speed improvements could be done on an object
> reference that is relatively robust to changes in the object tree and
> unless you are creating an IDE you would be very unlikely to need to
> do the LCB object reference repository thing.

I was pondering that whilst writing my 'experiment'. Whilst it says 'for
strict long ids', its strictness is more in the string structure (all
tokens lowercase, all integers 0 or start with 1, one space between
tokens etc. - this is mainly where the speed comes from - the 'parser'
in my experiment is basically an unrolled regular expression). It could
be evolved to parse more general control chunk chains over time.

Indeed, I was wondering whether 'minimal id' might be a reasonable name
- however, whatever the name, there's still the choice of stack short
name vs filename. I'd be happier about introducing a new id if we could
solve the multiple mainstack with same name issue too (or at least get a
step closer to it) - whilst it might be nice to think it could be done
with more appropriate search order, given the move towards libraries and
other such things I worry that no search order would ever solve the
problem really; and would end up with issues appearing in complex
circumstances which are hard to diagnose.

However, certainly, it would mean that the LCB idea is only something
you would need if you were writing a full IDE - as the problems the IDE
has only really come about because arbitrary script runs within it which
it can't control; in particular, locking messages around changes to
stack names, control ids, or control ownership.

Warmest Regards,

Mark.

--
Mark Waddingham ~ [hidden email] ~ http://www.livecode.com/
LiveCode: Everyone can create apps

_______________________________________________
use-livecode mailing list
[hidden email]
Please visit this url to subscribe, unsubscribe and manage your subscription preferences:
http://lists.runrev.com/mailman/listinfo/use-livecode
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Speed of control lookup (Was Re: Parent of Target)

** Clarence P Martin ** via use-livecode
On 08/12/2017 02:26 AM, Mark Waddingham via use-livecode wrote:

> I'd be happier about introducing a new id if we could
> solve the multiple mainstack with same name issue too

Yes, please.

--
  Mark Wieder
  [hidden email]



_______________________________________________
use-livecode mailing list
[hidden email]
Please visit this url to subscribe, unsubscribe and manage your subscription preferences:
http://lists.runrev.com/mailman/listinfo/use-livecode
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Speed of control lookup (Was Re: Parent of Target)

** Clarence P Martin ** via use-livecode
In reply to this post by ** Clarence P Martin ** via use-livecode

> On 12 Aug 2017, at 7:26 pm, Mark Waddingham via use-livecode <[hidden email]> wrote:
>
> I'd be happier about introducing a new id if we could solve the multiple mainstack with same name issue too (or at least get a step closer to it)

Hmm… what about giving stacks a meaningful ID… stack ID is completely useless right now as far as I can tell. What is currently the stack ID could be just an internal thing to maintain the ID sequence and stacks could be assigned a read only session ID. I very much doubt such a change would break any code but I guess I could be wrong there…

Perhaps better to make these references storable would be a UUID (ducks ;-). Maybe if _only_ stacks had a UUID they would be more palatable?

Cheers

Monte
_______________________________________________
use-livecode mailing list
[hidden email]
Please visit this url to subscribe, unsubscribe and manage your subscription preferences:
http://lists.runrev.com/mailman/listinfo/use-livecode
Loading...