Comments on: Just-in-time (JIT) binding
REBOL 3.0 will introduce a new type of binding: just-in-time
(JIT) binding. This is a long article, but I thought you would
be interested in the details, and I know you will not be shy in
providing your comments.
Currently, REBOL supports two types of binding:
| Definitional Context Binding (DCB) | Binding that occurs when you
define a block of data as the body of a specific datatype or
context. This is the normal REBOL binding as implemented by the
bind function. For example, the variables of a function are bound
to the function body when the make function! operation is
performed (or mezz function like func, function, etc.)
|
| Late Path Binding (LPB) | Binding that occurs when you use a path
that contains symbolic fields. This very late binding occurs during
the evaluation of the path itself. This happens mainly when you
access the fields of an object, and it is done so late to allow the
fields to be variables themselves.
|
These binding methods work fine for normal REBOL code; however, when
processing dialects of REBOL, they provide no benefit because the words
of the dialect never undergo definitional processing. Dialects are
just blocks, not specialized datatypes such as functions or objects.
During the implementation of the Rebcode project (which created a unique
model for a high performance REBOL virtual machine), it became obvious
that a very fast lookup method was needed for the opcodes of the VM.
When you specify an add or sub you don't want the interpreter
wasting any time trying to figure out what those opcode actually
mean.
Two solutions became obvious: use DCB or come up with a new type of
late binding, which for lack of a better term I will call
just-in-time binding (JIT). Both methods were considered; however,
because Rebcode was embodied in a function wrapper, it had the
opportunity for definitional processing. In addition, modification
of Rebcode blocks is not allowed after definition. So DCB was
perfect and improved the speed of Rebcode by three or four times.
So, what about other REBOL dialects? Can the performance of dialects
like draw and parse be improved? Yes, they can. Take the draw
dialect as an example. The keywords (commands) of the dialect are
evaluated quickly, but for large blocks (such as a large SVG image),
performance could be better. A significant amount of time is
required resolving the keywords each time the draw block is
evaluated.
Rebcode was implemented using the technique where a dialect
context defined the words of the dialect, and DCB was used to
bind the dialect block to that context. There is nothing fancy here.
However, this DCB method does not work well for dialect blocks like draw,
which are allowed to change dynamically. For instance, during an animation the
programmer may insert or remove commands in/from the draw block.
Such changes would invalidate the work done by a DCB process, but
the alternative would be to burden the programmer with maintaining the
bindings manually during each insertion, and we would prefer to avoid that.
Here enters JIT binding. In JIT, words are bound to the context as
they are encountered during the evaluation stream. Unlike LPB, the
words of the block are modified to hold their new bindings. They
are sticky. The next time the block is evaluated only a quick
check of the word's context is required, and no other action is
needed. If a new word has been inserted, the check fails, and the
JIT bind occurs.
The result is that dialects like draw and parse can evaluate much
faster, but without the need to prebind the words of the dialect
block. And, if the block remains substantially un-modified, the
evaluation speed of the dialect is very close to that of pure REBOL
code (requiring only the extra context check for each word).
Is there a downside to this method? Yes. Good design is all about
managing tradeoffs. It takes a small amount of time to setup the JIT
bind method prior to dialect evaluation. For very short blocks that
contain less than three or four keywords, the overhead of the JIT
setup could slow those blocks down. This is the kind of thing we
will need to test and evaluate. There may also be a slight penalty
for exceptions (errors, breaks, returns, throws) that occur during
evaluation of JIT dialects; however, such events should be rare for
most dialected code.
In conclusion: JIT binding is really just a evaluation-time style
of definitional context binding. It is believed that this type of
binding could provide substantial additional performance for the
dialects used in draw, parse, and others. It is also possible
that we could use JIT in place of LPB to improve performance for
object field access. That must be studied.
Note: this concept is still in the early design stage, and we should
know more soon. If you have any comments on this idea, I know that
you will happily post them here. Thanks.
21 Comments Comments:
Petr Krenzelok 11-Apr-2006 13:04 |
:)
just a average reboller's question - can we say, that once we get such an "immutable" blocks, we are closer to be able to compile part of rebol code?
-pekr- | maximo 11-Apr-2006 13:27 |
will it be possible to select JIT binding for contexts? | Brian Hawley 11-Apr-2006 13:41 |
This idea sounds great, particularly for dialects with keywords that can bind to a keyword context like rebcode. Another acronym, Keyword Context Binding (KCB)? For path evaluation though...
If you were compiling you could do data flow analysis to determine when the first word in the path referred to the same object. You could even use pseudotypes, like object signiatures or such in the compiler, to determine whether the object would follow the same pattern. In interpreted REBOL, how would you be able to tell this? You could manage the object signiature thing by converting words to field offsets (internally, since such a thing isn't visible with objects externally). You could manage the same object thing by comparing to the initial object value of the path and re-JITing when it is different - this would probably only be efficient for inner loops and references to the self field. Of course you could do direct JIT binding or DCB of get-word path members, since those refer to words in the local context anyways.
Perhaps you could compile a path into some efficient internal representation that would be evaluated by an internal dialect processor quickly. You could even add a rebcode op that would evaluate a semantically equivalent dialect directly, making path evaluation much more efficient there.
I can't wait to see how this all turns out. Following REBOL 3 development feels like reading a mystery novel - and you can't read the last page. | Carl Sassenrath 11-Apr-2006 13:44 |
Pekr: these are mutable. Prior discussion about copy or not is more about immutable.
Maximo: it could be possible. We would have to resurrect the old REBOL "in" function, perhaps as some kind of do/in context. But, I am not sure how much (if ever) it would get used. I would prefer to provide a function that allows users to invoke your own dialect evaluator (similar to reduce/only). | Carl Sassenrath 11-Apr-2006 13:49 |
Brian, ah... you want last chapter. Stay tuned to this channel. | Anonymous 11-Apr-2006 13:53 |
Path eval dialect pseudo-rebcode:
get.p result [get obj field a field b get c offset 2]
set.p [get obj field b get c offset 1] value | Brian Hawley 11-Apr-2006 13:57 |
(Sorry, that was me again. Haloscan keeps losing my name.)
The path eval dialect would hand off to the function + refinements evaluator when it hits a function. | Gregg Irwin 11-Apr-2006 15:35 |
Maybe not directly on-topic, but we've talked about a WITH function in the past (e.g. with object! block!), where the block is evaluated in the context of the object, to eliminate redundant path references, etc.
Just came to mind in the context of binding and execution. | Carl Sassenrath 11-Apr-2006 17:44 |
Gregg, and wasn't WITH in the REBOL alpha back in 1997? I think it was. So, good timing to bring it back. lol | Oldes 11-Apr-2006 17:44 |
WITH would be great:) At least if it will work like in ActionScript | Brian Hawley 11-Apr-2006 18:05 |
Wouldn't you be able to do the same thing as WITH by letting USE take an object as its first parameter and using its context? | Volker Nitsch 11-Apr-2006 18:21 |
:)
Good idea. WOuld that work on meazine level too?
Setting up an override-context with functions,
which is jit-bound in a similar way?
Could be a competition for parse, some people like functions more i guess.
For example they prefer functions over parse-rules for rpc.
Then, i got another implementation-idea. MAybeworth a short look. Works like this:
I guess the global context is a table,
And words could remember their index in it.
(even if bound somewhere else. needs an extra int).
Now you can create more tables, the draw table, the rebcode table etc.
The index for a word is the same in every table.
Now you populate the table with the dialects keywords.
Only once, when lib is loaded.
Then you can quickly find the draw-meaning of 'at, its rebcode-meaning etc.
simply by looking in the right table.
Advantage is, no extra setup-costs. good for the 4 keyword-dialects.
Disadvantage:
for words with non-keywords you have to look up twice,
in the draw-table and then in the words real context.
But if a high percentage is keywords and values, thats dwarfed.
Other issues:
- Maybe your current lookup outperforms the table-version significantly.
Then forget my idea!
- You need room in the value for extra index. I expect word-values have room.
- Space for table: Size of a table is ~4k*16byte ? cheap enough for a few dialects? | Gabriele 11-Apr-2006 18:21 |
:)
About the slowdown because of the JIT setup, does BIND need the same kind of setup? (If not, why does the JIT?) If so, then isn't the DCB case basically the same, but with the programmer having to care for binding?
(Or is the setup time actually due to the checks to avoid rebinding?) | Brian Hawley 11-Apr-2006 18:48 |
Parse and Draw keywords currently have to be looked up at runtime, every time they are encountered, like this:
switch/default aword [to [do something...]...] [not-keyword...]
Bind does that lookup once, ahead of time, and then sets the words to the context if they are found - after that no lookup is needed, like this:
if find acontext/words aword [aword/context: acontext]
aword
JIT would fixup the context of keywords on the fly, basically taking the overhead of bind and shifting it to the first run. Subsequent runs would be faster, like this:
any [
if acontext = aword/context [aword]
if find acontext/words aword [aword/context: acontext aword]
not-keyword...
] | Steeve 11-Apr-2006 20:02 |
Could we use the JIT binding, to have a native func, which inform if a block has been modified ? like:
>>touch my-block
== true
yes, my-block has been modified
with a refinement to get the list of modified index.
>> touch/list my-block
== [ 1 5]
meaning that my-block has been modified at index 1 and 5.
Would be very usefull when processes need to peform action only when changes are detected in a block and take less memory than to save an old copy of the block to perform comparison,
like: (old-block = my-block) | Anton Rolls 12-Apr-2006 1:26 |
Steeve, that's like QUERY on objects. That's very useful, would be good for blocks too. Maybe it would slow them down though. | Anton Rolls 12-Apr-2006 1:35 |
About WITH:
I was just yesterday thinking/needing a function similar to this and also similar to FOREACH. At first I thought to extend the functionality of FOREACH to also accept an object for it DATA argument, ie:
foreach [file size date] obj [
file: retrieve-filename
...
]
That would bind *only* the three specified words (where they are found) in the body block to the object.
Kind of like a binding intersection between two objects.
Perhaps a better function name for this is FORBIND. | Anton Rolls 12-Apr-2006 1:48 |
Such a power allows you to write code in the context of a large object eg. a large face object of unknown style and possibly unknown extra facets, without having to worry about words in your code clashing with any of those unknown facets.
Example:
Say I have a piece of code which processes a face object.
func [face /local picked][
repeat picked 3 [
do bind [
picked: data
] face
]
]
That works great on all different styles until one day the text-list style is invented along with its PICKED facet. Now the code breaks, because the 'picked word is bound to the face instead of remaining local to the func, as expected. | Anton Rolls 12-Apr-2006 1:51 |
That reminds me, BIND is another function which would be better with its arguments reversed.
(Maybe introducing WITH will alleviate that problem, though.) | Karol Gozlinski 12-Apr-2006 4:49 |
Is performace of executing functions with refinements also suffer from path bind-evaluation?
If yes, it is worth to make only them faster even if it would not be possible for object attributes selection. | Norman 12-Apr-2006 6:25 |
Actualy "un-modified" is what should be removed from the whole story. To make it even better also dymanicly modified blocks should be able in JIT....How dynamic must it be ? |
Post a Comment:
You can post a comment here. Keep it on-topic.
|