Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss
Lists related thoughts
35 views
Skip to first unread message
Jacob Wall
Dec 28, 2011, 7:12:30 PM12/28/11
to
Hello all,
First, I have a general System RPL question, does anyone know of a
>TCOMP replacement that is faster? By faster I mean for loops with
long lists, etc.
Second, is it possible with assembly to append a list "in-place" without
exploding and rebuilding a list?
Third, I will illustrate some basic situations that illustrate the
>TCOMP slow-down. Take the following System RPL program:
::
NULL{}
BINT101
ONE_DO
INDEX@
>TCOMP
LOOP
;
Very straight forward, start with a empty list, and add the loop index
to the list during each iteration, ending with a list of BINTS from 1 to
100. I tested with longer loops also, below are some timing numbers for
100, 200, 300, 400, 500, and 1000.
100 = 0.525s
200 = 2.057s
300 = 4.886s
400 = 10.938s
500 = 19.525s
1000 = 252.284s
It takes ~37 times longer to build a list 500 than a list of 100, and
~480 times longer for a list of 1000. The reasons are easy to explain
when considering how >TCOMP works, which explodes the list, adds the new
item, and then rebuilds the list. Of course the more objects are in the
list, the more memory is required, and the whole thing becomes much more
involved when there are many items in the list.
Now, to just build a list with a loop, not using >TCOMP is much faster,
as can be demonstrated with the following System RPL program:
::
BINT101
ONE_DO
INDEX@
LOOP
BINT100
{}N
;
This time the program simply returns the index of the loop during each
iteration, and at the end the list is built.
100 = 0.026s
200 = 0.060s
300 = 0.100s
400 = 0.139s
500 = 0.178s
1000 = 0.372s
This time building a list of 500 only takes ~6.8 times longer than a
list of 100, and only ~14.3 times longer to build a list of 1000, a much
more linear correlation.
Sometimes it becomes far too complicated, for example when working with
multiple lists and multiple loops, to perform all the actions involved
using only the stack. It is much easier to have three lists on the
stack and manipulating the contents as required than to have hundreds of
objects from three different lists on the stack and figuring out which
level of the stack you want to get or put something. So, hopefully with
a bit of explanation my two questions make slightly more sense?
First, does anyone know of a >TCOMP replacement that is faster? By
faster I mean for loops with long lists, etc.
Second, is it possible with assembly to append a list "in-place" without
exploding and rebuilding a list?
I searched hpcalc.org, did a Google search, and have not found anything
on this topic, although it is possible I didn't ask the right questions
for the search I suppose. Any input is appreciated.
Jacob Wall
First, I have a general System RPL question, does anyone know of a
>TCOMP replacement that is faster? By faster I mean for loops with
long lists, etc.
Second, is it possible with assembly to append a list "in-place" without
exploding and rebuilding a list?
Third, I will illustrate some basic situations that illustrate the
>TCOMP slow-down. Take the following System RPL program:
::
NULL{}
BINT101
ONE_DO
INDEX@
>TCOMP
LOOP
;
Very straight forward, start with a empty list, and add the loop index
to the list during each iteration, ending with a list of BINTS from 1 to
100. I tested with longer loops also, below are some timing numbers for
100, 200, 300, 400, 500, and 1000.
100 = 0.525s
200 = 2.057s
300 = 4.886s
400 = 10.938s
500 = 19.525s
1000 = 252.284s
It takes ~37 times longer to build a list 500 than a list of 100, and
~480 times longer for a list of 1000. The reasons are easy to explain
when considering how >TCOMP works, which explodes the list, adds the new
item, and then rebuilds the list. Of course the more objects are in the
list, the more memory is required, and the whole thing becomes much more
involved when there are many items in the list.
Now, to just build a list with a loop, not using >TCOMP is much faster,
as can be demonstrated with the following System RPL program:
::
BINT101
ONE_DO
INDEX@
LOOP
BINT100
{}N
;
This time the program simply returns the index of the loop during each
iteration, and at the end the list is built.
100 = 0.026s
200 = 0.060s
300 = 0.100s
400 = 0.139s
500 = 0.178s
1000 = 0.372s
This time building a list of 500 only takes ~6.8 times longer than a
list of 100, and only ~14.3 times longer to build a list of 1000, a much
more linear correlation.
Sometimes it becomes far too complicated, for example when working with
multiple lists and multiple loops, to perform all the actions involved
using only the stack. It is much easier to have three lists on the
stack and manipulating the contents as required than to have hundreds of
objects from three different lists on the stack and figuring out which
level of the stack you want to get or put something. So, hopefully with
a bit of explanation my two questions make slightly more sense?
First, does anyone know of a >TCOMP replacement that is faster? By
faster I mean for loops with long lists, etc.
Second, is it possible with assembly to append a list "in-place" without
exploding and rebuilding a list?
I searched hpcalc.org, did a Google search, and have not found anything
on this topic, although it is possible I didn't ask the right questions
for the search I suppose. Any input is appreciated.
Jacob Wall
John H Meyers
Dec 29, 2011, 6:30:37 AM12/29/11
to
On 12/28/2011 6:12 PM, Jacob Wall wrote:
> Sometimes it becomes far too complicated, for example when working with
> multiple lists and multiple loops, to perform all the actions involved
> using only the stack. It is much easier to have three lists on the stack
> and manipulating the contents as required than to have hundreds of
> objects from three different lists on the stack and figuring out which
> level of the stack you want to get or put something.
Have you heard of a "Meta object" -- I believe that's what they call
> Sometimes it becomes far too complicated, for example when working with
> multiple lists and multiple loops, to perform all the actions involved
> using only the stack. It is much easier to have three lists on the stack
> and manipulating the contents as required than to have hundreds of
> objects from three different lists on the stack and figuring out which
> level of the stack you want to get or put something.
an "exploded" list (or any composite), where each element occupies one
stack level, and an item count occupies the lowest of those levels.
It may not seem obvious how to swap, drop, concatenate, or otherwise perform
routine "stack operations" on entire meta-objects, but in fact
there is an entire group of predefined, supported SysRPL entry points
which already do these things, quite efficiently,
without requiring you to re-invent those commands.
Mika Heiskanen's short SysRPL "cheat sheet" on Goodies Disk #4
has a section summarizing such commands.
For example, When you have Meta new_item on the stack, then
something like SWAP #1+ appends the new item to the original Meta
(I don't have the entry points list at hand, so #1+ may not be
the right name, but I'm sure you can find the right name if not).
Jim Donnelly's old "handbooks" also mentioned that much of the OS relies upon
manipulating Meta objects in this way, and also listed many such operations
with supported ROM addresses, for use by UserRPL programmers via syseval.
[r->] [OFF]
Jacob Wall
Dec 29, 2011, 3:21:46 PM12/29/11
to
On 29/12/2011 3:30 AM, John H Meyers wrote:
> Have you heard of a "Meta object" -- I believe that's what they call
> an "exploded" list (or any composite), where each element occupies one
> stack level, and an item count occupies the lowest of those levels.
with meta objects.
> Mika Heiskanen's short SysRPL "cheat sheet" on Goodies Disk #4
> has a section summarizing such commands.
Jacob Wall
Dec 29, 2011, 5:55:31 PM12/29/11
to
On 29/12/2011 3:30 AM, John H Meyers wrote:
> For example, When you have Meta new_item on the stack, then
> something like SWAP #1+ appends the new item to the original Meta
> (I don't have the entry points list at hand, so #1+ may not be
> the right name, but I'm sure you can find the right name if not).
Yes, I just did some research, and SWAP#1+, aka SWP1+, is equivalent to
> something like SWAP #1+ appends the new item to the original Meta
> (I don't have the entry points list at hand, so #1+ may not be
> the right name, but I'm sure you can find the right name if not).
>TCOMP when substituting a meta for a list on the stack:
meta ob SWP1+
list ob >TCOMP
So, no surprise then that starting with a null meta, ZERO, and using the
same timing procedures as before:
::
ZERO
# 3E9
ONE_DO
INDEX@
SWP1+
LOOP
{}N
;
Compiling a list of 1000 runs in 0.647s. Also the commands "psh"
"roll2ND" "unroll2ND" and others similar to them are extremely fast when
you consider what is being done. It appears that setting up metas on
the stack prior to running long loops is definitely the way to go as
opposed to using lists.
Thanks for the nudge in the right direction John.
I am still curious about my second question, is it possible to add a
object to a list object "in-place" using assembly methods? With System
RPL the list is first exploded into a meta, ob is added to the end, and
the meta is then rebuilt into a list.
Jacob Wall
Dave Hayden
Dec 30, 2011, 4:03:59 PM12/30/11
to
On Dec 29, 5:55 pm, Jacob Wall <jac...@surv50.ca> wrote:
> I am still curious about my second question, is it possible to add a
> object to a list object "in-place" using assembly methods? With System
> RPL the list is first exploded into a meta, ob is added to the end, and
> the meta is then rebuilt into a list.
In general, no, you can't append to a list in-place. This is because
> I am still curious about my second question, is it possible to add a
> object to a list object "in-place" using assembly methods? With System
> RPL the list is first exploded into a meta, ob is added to the end, and
> the meta is then rebuilt into a list.
objects are stored contiguously in memory, so if you added something
to the end of a list, you would necessarily stomp on the object that
followed it.
If you were certain that the list was the last thing in TEMPOB then
you could probably do it. I don't know if >TCOMP already contains
this
optimization.
Another possibility is something of a cheat: you could put a large
placeholder object like string at the end of a list. To append a new
object, you could copy it over the beginning of the string and then
rewrite the string's prolog and size, adjusted accordingly. This
would
work if you knew the maximum size of the list up front. This is
messy,
but I think it would work.
Dave
Andreas Möller
Jan 1, 2012, 6:01:02 PM1/1/12
to
Hello Jacob,
hello Dave,
> I am still curious about my second question,
> is it possible to add aobject to a list object
> "in-place" using assembly methods?
in general it is possible. The 49/50 even has some ML entry points to
do this with objects that are *not* at the bottom of TEMPOB.
But all of this is relatively slow as David explained. If you really
need to “add” something a faster way would be to create a “new” TEMPOB
slot and then *copy* the data there from various sources (ensure that
no overlapping of your memory regions will happen!). You can either
reserve the exact amount of memory – if you know it or can calculate
it – or reserve all memory and then shrink the slot, or even easier
create a RAM-String in TEMPOB (which will be created in its own TEMPOB
slot) and then call the entry to shrink this string. This will not
only adjust the size of the string but also the size of the TEMPOB
slot.
There is another faster way I have been using in the past (but a
little bit more dangerous way as you have to do anything yourself):
Reserve all memory and do what you need to do and then don’t shrink
the string. Instead at the end of your used memory create a new object
so that the TEMPOB slot contains two objects, the one you want and the
one you don’t care about. As long as your object that you want is
referenced it will be o.k. for GC, the other “unwanted and
unreferenced” object will be delete with the next GC.
But be aware: each TEMPOB slot must hold valid objects, so ensure that
there where you “cut” your memory you write a correct prolog, etc, so
that it becomes an “unwanted” but valid object. Otherwise your machine
will crash.
I believe that this is the fastest way to work with memory, at least I
am not aware of a faster way. I am using this technique in my GUIMES
and in my translation packages and it works very well assuming that
you take care of everything. It is bullet proof if you do it right ;-)
> is first exploded into a meta
Working with meta’s is *very* fast as only the stack pointers are
actually moved and there are built-in ML routines for swapping two
blocks of memory.
That is the reason why psh is so fast, but be aware that it might
crash/warmstart in case of very low memory (but I do not think that it
has any practical use but I have watched/encountered this when I wrote
the “low memory handling” of TreeBrowser.
TreeBrowser uses several meta’s all the time to hold the shown data.
HTH and happy new year,
Andreas
http://www.software49g.gmxhome.de
hello Dave,
> I am still curious about my second question,
> "in-place" using assembly methods?
in general it is possible. The 49/50 even has some ML entry points to
do this with objects that are *not* at the bottom of TEMPOB.
But all of this is relatively slow as David explained. If you really
need to “add” something a faster way would be to create a “new” TEMPOB
slot and then *copy* the data there from various sources (ensure that
no overlapping of your memory regions will happen!). You can either
reserve the exact amount of memory – if you know it or can calculate
it – or reserve all memory and then shrink the slot, or even easier
create a RAM-String in TEMPOB (which will be created in its own TEMPOB
slot) and then call the entry to shrink this string. This will not
only adjust the size of the string but also the size of the TEMPOB
slot.
There is another faster way I have been using in the past (but a
little bit more dangerous way as you have to do anything yourself):
Reserve all memory and do what you need to do and then don’t shrink
the string. Instead at the end of your used memory create a new object
so that the TEMPOB slot contains two objects, the one you want and the
one you don’t care about. As long as your object that you want is
referenced it will be o.k. for GC, the other “unwanted and
unreferenced” object will be delete with the next GC.
But be aware: each TEMPOB slot must hold valid objects, so ensure that
there where you “cut” your memory you write a correct prolog, etc, so
that it becomes an “unwanted” but valid object. Otherwise your machine
will crash.
I believe that this is the fastest way to work with memory, at least I
am not aware of a faster way. I am using this technique in my GUIMES
and in my translation packages and it works very well assuming that
you take care of everything. It is bullet proof if you do it right ;-)
> is first exploded into a meta
actually moved and there are built-in ML routines for swapping two
blocks of memory.
That is the reason why psh is so fast, but be aware that it might
crash/warmstart in case of very low memory (but I do not think that it
has any practical use but I have watched/encountered this when I wrote
the “low memory handling” of TreeBrowser.
TreeBrowser uses several meta’s all the time to hold the shown data.
HTH and happy new year,
Andreas
http://www.software49g.gmxhome.de
Jacob Wall
Jan 2, 2012, 6:10:05 PM1/2/12
to
For some reason my replies in the last two days are not showing up,
could be my ISP I suppose, so I'm trying again from Google Groups
interface.
@Dave, from your explanation I gathered that while it may be
technically 'possible' it is not really practical.
@Andreas, thanks for your explanation, it sounds fairly involved to
implement something like that from scratch!
> I believe that this is the fastest way to work with memory, at least I
> am not aware of a faster way. I am using this technique in my GUIMES
> and in my translation packages and it works very well assuming that
> you take care of everything. It is bullet proof if you do it right ;-)
So in general your method is faster than using metas with "get1 SWP1+"
or similar when you have for example two or more metas on the stack,
maybe a few thousand levels of the stack occupied?
> > is first exploded into a meta
> Working with meta’s is *very* fast as only the stack pointers are
> actually moved and there are built-in ML routines for swapping two
> blocks of memory.
> That is the reason why psh is so fast, but be aware that it might
> crash/warmstart in case of very low memory (but I do not think that it
> has any practical use but I have watched/encountered this when I wrote
> the “low memory handling” of TreeBrowser.
> TreeBrowser uses several meta’s all the time to hold the shown data.
I have come across the low memory situation also, the way I have been
dealing with it is by calculating if enough memory 'should' be
available and then stopping long loops from starting in the first
place if I'm going to be building very 'big' metas/lists. This of
course is not the best way to deal with the situation, especially
since my calculations are usually based on some assumptions that
cannot be completely determined beforehand...
> HTH and happy new year,
Happy new year, and thanks for your explanations.
Jacob Wall
could be my ISP I suppose, so I'm trying again from Google Groups
interface.
@Dave, from your explanation I gathered that while it may be
technically 'possible' it is not really practical.
@Andreas, thanks for your explanation, it sounds fairly involved to
implement something like that from scratch!
> I believe that this is the fastest way to work with memory, at least I
> am not aware of a faster way. I am using this technique in my GUIMES
> and in my translation packages and it works very well assuming that
> you take care of everything. It is bullet proof if you do it right ;-)
or similar when you have for example two or more metas on the stack,
maybe a few thousand levels of the stack occupied?
> > is first exploded into a meta
> Working with meta’s is *very* fast as only the stack pointers are
> actually moved and there are built-in ML routines for swapping two
> blocks of memory.
> That is the reason why psh is so fast, but be aware that it might
> crash/warmstart in case of very low memory (but I do not think that it
> has any practical use but I have watched/encountered this when I wrote
> the “low memory handling” of TreeBrowser.
> TreeBrowser uses several meta’s all the time to hold the shown data.
dealing with it is by calculating if enough memory 'should' be
available and then stopping long loops from starting in the first
place if I'm going to be building very 'big' metas/lists. This of
course is not the best way to deal with the situation, especially
since my calculations are usually based on some assumptions that
cannot be completely determined beforehand...
> HTH and happy new year,
Jacob Wall
0 new messages