Comments on: REDUCE/into and COMPOSE/into

Carl Sassenrath, CTO
REBOL Technologies
27-May-2009 23:44 GMT

Article #0208
Main page || Index || Prior Article [0207] || Next Article [0209] || 9 Comments || Send feedback

When building large block series, it is very common to write:

repend series [a b c]

Which is shorthand for:

append series reduce [a b c]

The evaluated results of a, b, and c are appended to the series.

If this is done a lot, a large number of temporary series are generated, which take memory and also must be garbage collected later.

An optimizing refinement in reduce and compose have been added to the A55 release:

reduce/into [a b c] tail series
compose/into [a (b) c] tail series

These require no intermediate storage.

The savings can be seen if you do:

series: make block! 30000
repeat n 10000 [append series reduce [n + 1 n - 2 n * 3]]

Now, replace the repeat line with:

repeat n 10000 [reduce/into [n + 1 n - 2 n * 3] tail series]

You will see the savings of 10000 block allocations.

Many thanks to Brian Hawley for lobbying for this refinement in R3.



Brian Hawley
27-May-2009 23:56:18
I noticed that all of your examples are appending on the end of the series, which will definitely be the most common usage in optimal code. However, you don't necessarily have to insert at the tail of the buffer - you can insert anywhere you like.

The interesting part of the /into option is that it uses INSERT semantics. This was chosen because INSERT is the most basic series operation. You can use INSERT to implement APPEND if you like, but you can't use APPEND to implement INSERT without temporary series. If we were going to add one option for this, we picked the most general one.

One thing you will notice in hand-optimized REBOL code is chained inserts into preallocated buffers. This code pattern saves intermediate blocks and tends to be faster, but sometimes you can see 4 or 5 INSERT functions in a row. This can get confusing, particularly if they have different options. Even so, you still see it because it is the most efficient code pattern.

We can do better now. With functions with the /into option, you can do a drop-in replacement for INSERT, or any number of chained INSERTs. You don't even necessarily have to know how much has been inserted, because the tail of the inserted data is returned from the function when /into is used, just like it is with INSERT. You don't even have to replace all of the chain if you like.

R3 has already added /into to a few mezzanine functions: COLLECT, EXTRACT and REWORD. Any of these can be used already. The real improvements will come from REDUCE/into and COMPOSE/into though - with these we can really optimize the mezzanine code and make R3 faster and more memory efficient.

I've been looking forward to this for months :)

Maxim Olivier-Adlhoch
28-May-2009 1:12:45
this is a serious enabling extension to rebol!

would have used it SOOOO often.

Maxim Olivier-Adlhoch
28-May-2009 2:33:40
this could probably reduce rebol's memory consumption by a few thousand block allocations for each massive refresh of larger liquid-paint canvases (recycled afterwards, but still useless CPU usage).
28-May-2009 2:36:34
This is a line of code we use in the style area-tc, to rebuild a draw block. It looks a bit insane, but we need it to prevent any memory overhead in that code location, because it can be called thousand of times per second when the style is scrolled.

out-style: insert insert insert insert insert insert insert insert out-style
		'pen color/2 'fill-pen color/2 'box
		as-pair abs-x 7 as-pair (f/x * length? str) + abs-x 7 + f/y 3

Now with the new refinement, it can be done with a not insane syntax ;-)

out-style: reduce/into ['pen color/2 'fill-pen color/2 'box as-pair abs-x 7 as-pair (f/x * length? str) + abs-x 7 + f/y 3] out-style

28-May-2009 7:56:34
I find the syntax a bit strange. It feels like the arguments are swapped.

I could understand:

repend/into series [a b c]


reduce/into [a b c] series

disturbs the normal flow of REDUCE. Which is return the reduced left-hand-side.

Brian Hawley
28-May-2009 10:16:16
Sorry, Robert, that's a REBOL thing. You can't have left-hand-side optional arguments.
Anton Rolls
28-May-2009 12:56:13
Great!! I just read a bit about the INSERT chaining argument. Yes, I have been chaining INSERT in DRAW blocks and would definitely value the return after the insertion. (Never mind those newbies who don't understand it yet and complain when they get confused.)
18-Jun-2009 0:42:21
Testing simple blog captcha method.
Carl Sassenrath
18-Jun-2009 0:52:38
Let me know if there are any problems posting comments now.

Post a Comment:

You can post a comment here. Keep it on-topic.


Blog id:



 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.

Updated 24-Mar-2017 - Edit - Copyright REBOL Technologies -