REBOL 3.0

Comments on: Just-in-time (JIT) binding

Carl Sassenrath, CTO
REBOL Technologies
11-Apr-2006 16:39 GMT

Article #0010
Main page || Index || Prior Article [0009] || Next Article [0011] || 21 Comments || Send feedback

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.

Name:

Blog id:

R3-0010


Comment:


 Note: HTML tags allowed for: b i u li ol ul font span div a p br pre tt blockquote
 
 

This is a technical blog related to the above topic. We reserve the right to remove comments that are off-topic, irrelevant links, advertisements, spams, personal attacks, politics, religion, etc.

REBOL 3.0
Updated 28-Mar-2024 - Edit - Copyright REBOL Technologies - REBOL.net