golly-test Mailing List for Golly

I think this is the best solution.

On 12/12/05, Andrew Trevorrow <an...@tr...> wrote:
> Mostly to Tom and Jason:
>
> I asked the wx-dev list about why IDC_CROSS is commented out in cursor.cp=
p.
> The change was made by Julian Smart (originator of wxWidgets) because
> on his XP Pro system he got an I-beam cursor.  Other people can't seem
> to reproduce the problem but I suspect it's not going to change.
>
> So, instead of patching cursor.cpp I think we're better off using a
> different solution.  I've added bitmaps/cross_curs.bmp for use in
> the Win app -- it has a white border and is visible on any background.
> Not quite as nice as an XOR cursor but it'll do (and is identical to
> the cross cursor used in the Mac app).
>
> Andrew
>
>
> -------------------------------------------------------
> This SF.net email is sponsored by: Splunk Inc. Do you grep through log fi=
les
> for problems?  Stop!  Download the new AJAX search engine that makes
> searching your log files as easy as surfing the  web.  DOWNLOAD SPLUNK!
> http://ads.osdn.com/?ad_id=3D7637&alloc_id=3D16865&op=3Dclick
> _______________________________________________
> Golly-test mailing list
> Gol...@li...
> https://lists.sourceforge.net/lists/listinfo/golly-test
>

Mostly to Tom and Jason:

I asked the wx-dev list about why IDC_CROSS is commented out in cursor.cpp.
The change was made by Julian Smart (originator of wxWidgets) because
on his XP Pro system he got an I-beam cursor.  Other people can't seem
to reproduce the problem but I suspect it's not going to change.

So, instead of patching cursor.cpp I think we're better off using a
different solution.  I've added bitmaps/cross_curs.bmp for use in
the Win app -- it has a white border and is visible on any background.
Not quite as nice as an XOR cursor but it'll do (and is identical to
the cross cursor used in the Mac app).

Andrew

> The CutPaste discussion with Brice has reminded me of my second[1] most important application of LifeLab, the evolution of minimally disrupted agars, which relies on a feature which Andrew has suggested he wants to put into Golly down the track: "Tile With Selection".

Yep, that's one of the first things needed if and when I add support
for toroidal universes.  That's not going to happen soon unfortunately.
I'm allowing myself another 2 months or so of full-time work on Golly
and then I'll have to start utilizing my wxWidgets skills on projects
that are likely to earn some income!

In the short term, would a "Tile Selection" item be of any use?
That is, the current selection would be tiled with the current clipboard
pattern, clipping at the right and bottom edges where necessary.
That would be simple to implement.

Another LifeLab function I haven't yet added to Golly is "Invert Selection"
which simply swaps cell states in the current selection.  Would anybody
find that useful?  Also trivial to implement.

> I'm not trying to suggest any near term changes, but it seems the discussion on CutPaste has taken us to places where it might be easy to think about the implications of persistent non-empty backgrounds and how hard it might be to factor them into the methods which assume an empty background.

Very hard, I'd say.

Andrew

Brice, the high level answer to your question is that the proportion of 
"evolvable sub-patterns" can be anything between asymptotic to zero 
(Class 1 rules) and unity (reversible rules).

Trying to explore the problem space in the small, and just for Life, 
has been my primary therapeutic distraction for longer than I'd ever 
admit and even then I've only come to an opinion that common small 
sub-patterns have on average of order 2 "naturally occurring" 
non-trivial precursor patterns. Certainly the rate of increase in the 
number of potentially persistent seed patterns as the number of live 
cells increases swamps the rate of shrinkage to the point I doubt 
whether we will ever get exhaustive stats for the full range of seeds 
with much more than ten live cells, although an approach like the one 
you have forming here may stretch that a little.

I'd love to be able to contribute more than generalist commentary, but 
that is mostly what I do. I'm certainly looking forward to any hard 
"basin-of-attraction" data which could shed light on some of the 
dimmest corners of complex systems.


On 04/12/2005, at 3:35 PM, Brice wrote:

> From a more mathematical point of view my idea is predicated on the 
> assumption that for a given rule, the set of possible evolvable 
> sub-patterns (tiles say) is much smaller than the total set of 
> possible tiles. It seems like the choice of tile size or the choice of 
> gen-aggregation (8^n) would be dominant here. I guess the real problem 
> is to determine which conditions are ammenable to an hlife-only 
> solution (no switching), 'cause that's the simplest way to go. It also 
> seems relevant that for collision runs I would be starting with a 
> certain subset of life patterns. So this could restrict the set of 
> possible evolvable subpatterns more than if using say random starting 
> conditions. This is a basin-of-attraction kind of issue which is far 
> beyond my abilities except in the abstract.
>

Tony Smith
Complex Systems Researcher
Meme Media
Melbourne, Australia
http://www.meme.com.au/

Hi Andrew, sorry that was not a great choice of words, not even a good  
choice:

> I'm puzzled why you find the progress window to be an embarassing hack.

I meant mostly that in the context of golly being super fast at running  
patterns it was *startling* to be presented with a 15min progress box for  
a "simple" cut/paste in a nearly empty universe. At first I assumed it was  
a temporary "hack" put in place while you found time to fix the problem.  
Later on in my email ramblings I conceded that a progress box was/is  
inevitable because there is no practical way to avoid all overload  
situations. A faster algorithm can always be crushed by a larger cut/paste  
op. So my position boils down to: the progress box just needs more  
explanatory text so that people understand whats going on when they get  
one. I have some limited understanding of the data structures and  
algorithms under the hood so I caught on. I'd be surprised if the progress  
box gets positive or neutral reactions from people. But it probably  
doesn't get triggered very often.

People understand tradeoffs are a fact of life. But most people won't  
understand why cut/paste performance is one of those tradeoff situations.  
It's sooo counterintuitive after watching golly run.

The edit-only space sounds good since you can tune it for its purpose. But  
it will consume more memory than the runtime quadtrees, so there will  
always be patterns you can run but can't edit because they've grown to big  
to convert in available memory.

Golly _is_ great!
-brice

-- 
Using Opera's revolutionary e-mail client: http://www.opera.com/mail/

Brice:

> My main concern was exactly that Golly is ultra fast, but *permits* the user to attempt a cut/paste operation which stalls for 10s of minutes. Duh, the data structures are not designed for this, and why would you want to do that anyhow? But you *can*, and the progress bar hack is just embarrassing as it stands.

I'm puzzled why you find the progress window to be an embarassing hack.
What is the alternative?  Are you saying we should not permit operations
that are likely to take more than X minutes?  That seems too harsh --
someone might want to do a big, one-off task (eg. rotate caterpillar)
and be quite happy to wait a long time for it to complete.

Or maybe you're suggesting we put up a dialog saying "This operation is
going to take about X minutes.  Do you want to continue?".  So what do
we do if the user decides to continue?  Just display a busy cursor with
no feedback on how long before the task finishes?  Not very friendly.
No, we'd need to display ... a progress window!  So asking the initial
question is just a waste of time.

Displaying a progress window that lets you cancel a lengthy operation
is the only sensible approach IMHO.

> If you do augment the quadtrees for cut/paste, etc, maybe it should be temporary, during interactive pattern manipulations. Runtime should go back to the dense quadtrees because they're already near-optimal for generation.

There's a potentially good idea here.  Let's look at what Golly currently
does when the user decides to do a paste:

1. The current clipboard data is dumped to a temporary file.  This is
   done so we can use our file reading routine (in step 3) to load in
   the data which might be in RLE, Life 1.05/06, or some other format.

2. A temporary, empty universe is created (qlife is used because its
   setcell/getcell calls are faster).

3. The temporary file is read into the temporary universe.

4. The pattern in the temporary universe is pasted into the current
   universe at the requested location.  (This is the step that can
   be improved by using nextcell rather than getcell.)

5. The temporary file and temporary universe are deleted.

Now, let's look at step 2.  Instead of creating a qlife universe,
maybe we could create a new "elife" universe (e for edit-only) that
is optimized for editing operations; ie. it would have no generating
capability, and its data structures would be designed so that the
setcell/getcell/nextcell calls would be very fast.

In fact, maybe we could extend the idea even further and use elife
for *all* editing ops.  Instead of using setcell/getcell/nextcell
primitives to do a cut/copy/paste/flip/rotation, we convert the
current qlife/hlife universe to elife form, call a single high-level
editing routine (implemented in elifealgo.cpp) and then convert the
result back to a qlife/hlife universe.  The only potential snag is
whether the conversion from qlife/hlife to elife and back can be
made fast enough to justify such an approach.  If we keep the current
1B x 1B edit limits then the elife data structures wouldn't need to
use bigints.

Andrew

When to switch? We may not be on the exact same page yet. My idea is to  
let hlife cache the accumulated experience from collision to collision. So  
yes the initial period will be one of the hash table expanding rapidly.  
But my conceptual idea was that after a while, most of the collisions  
would be mostly cache-positive at the sub-pattern (tile) level. At a  
sub-pattern level the collisions would often be recomputing familiar  
ground. Maybe shifted, but after a while all relavent shifts would be in  
the cache. The tuning would not be when to switch algorithms, but what  
step to use -- how many levels to canonicalize during the runs. In my  
scenario of alowing 500gens per collision, should hlife be aggregating 8^1  
or 8^2 gens? Which way will produce better cache hit rates over the long  
term of the total collision space? Which way will conserve cache memory in  
the long term?

The first obvious stumbling point is that there may be no easy way to  
decouple the cache from the running patterns. In other words, if I run a  
pattern with hlife, then I clear the universe but don't call clearcache(),  
and then I restart the same pattern from the initial cell configuration,  
does the cache from the first run accelerate the second run? My conceptual  
understanding of the algorithm is that the live universe is represented by  
a quadtree of pointers into the hashtable cache. So can I clear the  
pointer set but leave the cache in place? The next run would build a new  
set of pointers into the persistent cache. Over the long run this seems  
like it could be very fast for large problem spaces that are bounded in  
specific ways. Memory management would be something like deleting least  
used hash table entries periodically. An LRU policy could be applied  
between runs. Another level of tuning would be LRU policy versus maximum  
cache size. This is going to run in the background for months so it can't  
take everything like golly can.

In my gencols scenario, no single pattern run would ever consume much  
memory, but over time the cache could grow if the problem space turned out  
to cover a large fraction of the combinatorial space at the tile level.

Actually I think I understand your "when to switch" comment just now. You  
are suggesting that the initial x-gens of *each* collision be run with say  
qlife and succeding gens be run with a cumulative-cache hlife? The switch  
point would either have to be fixed and pre-determined empiricaly or  
detected on the fly. That sounds like a very tough problem to decide.  
Maybe I'm not asking the right question here. When I run metacatacryst out  
to the end of time is the memory consumption dominated by the cache or by  
the set of pointers into the cache? I was imagining the later. For  
something like hlife+gencols where patterns are individually bounded in  
small space, the cache could have a larger percentage of total memory  
because the small pointer trees would be torn down after every run.

 From a more mathematical point of view my idea is predicated on the  
assumption that for a given rule, the set of possible evolvable  
sub-patterns (tiles say) is much smaller than the total set of possible  
tiles. It seems like the choice of tile size or the choice of  
gen-aggregation (8^n) would be dominant here. I guess the real problem is  
to determine which conditions are ammenable to an hlife-only solution (no  
switching), 'cause that's the simplest way to go. It also seems relevant  
that for collision runs I would be starting with a certain subset of life  
patterns. So this could restrict the set of possible evolvable subpatterns  
more than if using say random starting conditions. This is a  
basin-of-attraction kind of issue which is far beyond my abilities except  
in the abstract.

Have to think more and read the code / try it... I'm getting the feeling  
this is going to be an empirical hit or miss kind of problem.

Thanks!
-brice


On Sat, 03 Dec 2005 22:07:26 -0500, Tom Rokicki <ro...@gm...> wrote:

> Actually, this is a very interesting topic, one that could have
> amazing results.
>
> The problem is of course initially collisions/etc. are random,
> so will break the hash table, but once that randomness
> dies down, tracking further evolution with hlife may indeed
> pay massive dividends.
>
> The trick is, can you figure out when to switch?  :-)
>
> On 12/3/05, Brice <bri...@ve...> wrote:
>> Hi Tom, I have a question unrelated to the cut/paste thing. I am  
>> rewriting
>> gencols because I want to explore a very large collision/combinatorial
>> space -- just to see what's out there. Gencols is not particularly
>> efficient for what I have in mind. I need more speed and more
>> sophisticated result filtering. On the speed front I was thinking about
>> grafting in Alan Hensel's java algorithm as C code. But yesterday I
>> started thinking about hlife.
>>
>> I'm curious if hlife can be used to cache life computations over a large
>> set of independent small pattern runs. The search space is so large that
>> I'd be running the program in the background for weeks or months or
>> forever. After a short while, each new collision configuration would be
>> recalcuating sub-patterns that had already been seen. Sounds like a job
>> for hlife.
>>
>> My idea is to clear the live cell universe without clearing the hash  
>> table
>> of canonicalized results, so the pre-computed results are available for
>> the next collision run.
>>
>> I know that real performance would depend on usage, and it may be that
>> recomputing familiar patterns with a hensel/qlife algorithm might run
>> faster due to processor cache issues. Benchmarking required. But do you
>> see any glaring reason why hlife (golly version or 0.96) would perform
>> badly? Initial patterns would be small (100x100?) and total gens per
>> collision probably <500 so final patterns would be bounded by maybe
>> 400x400 or so. Since all the collisions are similar and the total area  
>> is
>> bounded it is reasonable to think that the hash table would behave well
>> over weeks and months of aggregate use.
>>
>> A simple yea, nea is what I'm after. It may take me a while to  
>> understand
>> the subtleties of the code since I'm also teaching myself C at the same
>> time.
>>
>> Thanks!
>> -brice
>>
>>
>> -------------------------------------------------------
>> This SF.net email is sponsored by: Splunk Inc. Do you grep through log  
>> files
>> for problems?  Stop!  Download the new AJAX search engine that makes
>> searching your log files as easy as surfing the  web.  DOWNLOAD SPLUNK!
>> http://ads.osdn.com/?ad_id=7637&alloc_id=16865&op=click
>> _______________________________________________
>> Golly-test mailing list
>> Gol...@li...
>> https://lists.sourceforge.net/lists/listinfo/golly-test
>>
>
>
> -------------------------------------------------------
> This SF.net email is sponsored by: Splunk Inc. Do you grep through log  
> files
> for problems?  Stop!  Download the new AJAX search engine that makes
> searching your log files as easy as surfing the  web.  DOWNLOAD SPLUNK!
> http://ads.osdn.com/?ad_idv37&alloc_id865&op=click
> _______________________________________________
> Golly-test mailing list
> Gol...@li...
> https://lists.sourceforge.net/lists/listinfo/golly-test



-- 
Using Opera's revolutionary e-mail client: http://www.opera.com/mail/

Actually, this is a very interesting topic, one that could have
amazing results.

The problem is of course initially collisions/etc. are random,
so will break the hash table, but once that randomness
dies down, tracking further evolution with hlife may indeed
pay massive dividends.

The trick is, can you figure out when to switch?  :-)

On 12/3/05, Brice <bri...@ve...> wrote:
> Hi Tom, I have a question unrelated to the cut/paste thing. I am rewritin=
g
> gencols because I want to explore a very large collision/combinatorial
> space -- just to see what's out there. Gencols is not particularly
> efficient for what I have in mind. I need more speed and more
> sophisticated result filtering. On the speed front I was thinking about
> grafting in Alan Hensel's java algorithm as C code. But yesterday I
> started thinking about hlife.
>
> I'm curious if hlife can be used to cache life computations over a large
> set of independent small pattern runs. The search space is so large that
> I'd be running the program in the background for weeks or months or
> forever. After a short while, each new collision configuration would be
> recalcuating sub-patterns that had already been seen. Sounds like a job
> for hlife.
>
> My idea is to clear the live cell universe without clearing the hash tabl=
e
> of canonicalized results, so the pre-computed results are available for
> the next collision run.
>
> I know that real performance would depend on usage, and it may be that
> recomputing familiar patterns with a hensel/qlife algorithm might run
> faster due to processor cache issues. Benchmarking required. But do you
> see any glaring reason why hlife (golly version or 0.96) would perform
> badly? Initial patterns would be small (100x100?) and total gens per
> collision probably <500 so final patterns would be bounded by maybe
> 400x400 or so. Since all the collisions are similar and the total area is
> bounded it is reasonable to think that the hash table would behave well
> over weeks and months of aggregate use.
>
> A simple yea, nea is what I'm after. It may take me a while to understand
> the subtleties of the code since I'm also teaching myself C at the same
> time.
>
> Thanks!
> -brice
>
>
> -------------------------------------------------------
> This SF.net email is sponsored by: Splunk Inc. Do you grep through log fi=
les
> for problems?  Stop!  Download the new AJAX search engine that makes
> searching your log files as easy as surfing the  web.  DOWNLOAD SPLUNK!
> http://ads.osdn.com/?ad_id=3D7637&alloc_id=3D16865&op=3Dclick
> _______________________________________________
> Golly-test mailing list
> Gol...@li...
> https://lists.sourceforge.net/lists/listinfo/golly-test
>

Hi Tom, I have a question unrelated to the cut/paste thing. I am rewriting  
gencols because I want to explore a very large collision/combinatorial  
space -- just to see what's out there. Gencols is not particularly  
efficient for what I have in mind. I need more speed and more  
sophisticated result filtering. On the speed front I was thinking about  
grafting in Alan Hensel's java algorithm as C code. But yesterday I  
started thinking about hlife.

I'm curious if hlife can be used to cache life computations over a large  
set of independent small pattern runs. The search space is so large that  
I'd be running the program in the background for weeks or months or  
forever. After a short while, each new collision configuration would be  
recalcuating sub-patterns that had already been seen. Sounds like a job  
for hlife.

My idea is to clear the live cell universe without clearing the hash table  
of canonicalized results, so the pre-computed results are available for  
the next collision run.

I know that real performance would depend on usage, and it may be that  
recomputing familiar patterns with a hensel/qlife algorithm might run  
faster due to processor cache issues. Benchmarking required. But do you  
see any glaring reason why hlife (golly version or 0.96) would perform  
badly? Initial patterns would be small (100x100?) and total gens per  
collision probably <500 so final patterns would be bounded by maybe  
400x400 or so. Since all the collisions are similar and the total area is  
bounded it is reasonable to think that the hash table would behave well  
over weeks and months of aggregate use.

A simple yea, nea is what I'm after. It may take me a while to understand  
the subtleties of the code since I'm also teaching myself C at the same  
time.

Thanks!
-brice

The CutPaste discussion with Brice has reminded me of my second[1] most 
important application of LifeLab, the evolution of minimally disrupted 
agars, which relies on a feature which Andrew has suggested he wants to 
put into Golly down the track: "Tile With Selection".

(I should note here that I am almost entirely motivated by searches for 
emergent complexity, resilience, et al in systems with simple starting 
conditions, of which agars are a good example, rather than being 
motivated by heavy engineering.)

I'm not trying to suggest any near term changes, but it seems the 
discussion on CutPaste has taken us to places where it might be easy to 
think about the implications of persistent non-empty backgrounds and 
how hard it might be to factor them into the methods which assume an 
empty background.

Ultimately I'd like to be able to go places with 2D CAs which are 
analogous to the way signals in Wolfram Rule 110 turn out to be phase 
transitions on a space filling background.

[1] My most important application of LifeLab is (narrow) cylindrical 
universes which also make use of "Tile With Selection" and would be 
further enhanced by adding cylindrical as well as toroidal wrapping, 
the latter having also been foreshadowed for Golly as well as being 
necessary to avoid edge effects with most agars.


Tony Smith
Complex Systems Researcher
Meme Media
Melbourne, Australia
http://www.meme.com.au/

Tom, at the risk of being useless, I'm going to hazard a few more  
thoughts. I'm sure you've already visited them before. Some of this was in  
my other reply Re:Re:... My comments may not be useful, but I've always  
been facinated with data structure tradeoffs, so I'll ramble a bit. You  
don't have to reply.

1.) It sounds like you absolutely do not want to augment the leaf or  
near-leaf nodes with location info which would facilitate lateral walks.  
So the alternate ways to access the tree boil down to walking the leafs in  
cartesian order (which I can imagine maps to RLE nicely since you can  
compute skips from the parent traversals, esp. if you buffer multiple  
scanlines at once), or tree order, or building a secondary external index  
for the purpose of speeding up manipulations.

2.) Copy/Cut to a quadtree intermediate seems on the face of it trivial.  
You already have quadtree support code. I guess the complication comes  
with the paste. Either you do a tree merge or you find the live cells in  
the source and setcell() them one at a time in the destination. Average  
case would be good but worst case horrible. Clearing large contiguous  
portions of a quadtree would also seem to be trivial since you can simply  
cut the subtree. Complications come from the cut/paste areas not aligning  
with the quadtree subdivisions. And you may be trying to prevent memory  
fragmentation to improve cache performance. Are Golly's quadtrees cache  
friendly at all?

3.) Going up/down the full tree is not so bad for live cells since  
populations will almost always be sparse. The main problem is getting a  
list of live cells. The naive (x,y) scans do full tree traversals for  
every tuple and most cells are non-existant. I imagine nextcell() does  
alot of tree traversals because you imply you're only tracking a single  
bit scanline at a time. Ideally you need a routine that will return a list  
of live cells within a given rectangle. This is only needed during  
interactive manipulations (or under script control). Most  
copy/paste/rotate/identify operations I can think of can be done  
conceptually using an unordered list of live cells. Sorting by Cartesian  
order seems only useful when outputing RLE for example. But an unordered  
live cell list must contain coordinate info. A list of pointers into the  
tree doesn't cut it because there are no parent pointers to follow in  
order to deduce coordinate locations.

4.) You could implement a subtree walk that returns a list of live cell  
coordinates in walk-order. Filtered based on clipping area. This would be  
somewhat faster than the nextcell() raster-RLE but maybe only by a  
constant. Returned coordinates could be factored by the subtree's location  
in the hierarchy, or coded as quadtree addresses rather than bigint  
cartesian coordinates. For flips and 90degree rotations the quadtree  
adressess should be easy enough to manipulate. They are also relative to  
the root of the subtree and so could be applied directly to the  
destination quadtree when pasting. This becomes a leafwise tree merge. By  
"quadtree address" I mean the bit-interleaved traversal decision sequence.  
There are fast ways of handling quadtree addresses. See  
http://ftp.arl.mil/ftp/pub/Gems/original/BitInterleaving.c for instance.

5.) Caveat: hlife can easily cause unbounded populations, so the linear  
with population idea can easily get out of hand here. What if I run  
metacatacryst for while then decide I'd like to see two of them fight it  
out? Copy flip paste. Golly UI lets you try it (but the more efficient way  
would be to restart the simulation with the two patterns appropriately  
spaced which would require scripting to do acurately). Quadtree algorithms  
would seem the only safe way with hlife. Since things are canonicalized  
there, it may be more efficient to transfer a mega qlife pattern over to  
hlife space for mega cut/paste, etc... iff you implement efficient  
quadtree edits for hlife. Most qlife mega patterns will be quite redundant.

6.) Is it reasonable to engineer a sparse data structure to perform well  
under worst case dense loading/querying? Because Golly deals with  
conceptually mega structures it will always always be vulnerable to  
overloads when conditions stray towards worst cases. The only sane way to  
deal with it is to trap the worst case situations gracefully and tell the  
user why they can't do something. Or tell them the cost and let them  
decide to do it anyway. You could jokingly calculate Moore's law for them  
and tell them to come back in x years when machines can handle the  
requested op in reasonable time.

Thanks for all the info!
-brice


On Sat, 03 Dec 2005 16:07:18 -0500, Tom Rokicki <ro...@gm...> wrote:

> For the sake of discussion I'm gonna play *really* fast and loose
> with complexity theory, but here goes.
>
> Without loss of generalization, let's define n as the width and
> height of the cut/paste area, u as the width and height of the
> universe, and p as the population of the cut/paste area.
>
> The universe tree in both qlife and hlife is of depth O(log(u)).
> Setcell/getcell take time O(log(u)) because they have to walk.
> The naive cut/paste that traverses x/y therefore takes time
> O(n^2 log(u)).  This is really slow.  Some of the cut/paste-type
> operations in golly still take that long.
>
> I implemented a nextcell() routine that returns the next cell
> in cartesian order.  Analysis of its runtime is difficult, but
> amortized it's probably O(log(u)).  If we use this operation in
> cut/paste, and ignoring the cost of clearing the destination
> beforehand if necessary, then we can cut down the cut/paste
> time to O((p+n)log(u)) (the n is there because nextcell works on
> a raster-row by raster-row basis, and a more precise formula
> is likely to be O((p+n*log(u))log(u)) but like I said, analysis is
> difficult.)  This is still much better than the naive approach, and
> it is what we use in several other places in golly.
>
> Both of these methods permit storage of an intermediate
> result (a cut) in the RLE format, which itself is roughly
> O(p) (but not exactly; a factor describing the average
> sparseness of the pattern needs to go in there too).  Since
> this doesn't appreciably slow things down, and since RLE
> is nice to cut/paste anyway, we use RLE as an intermediate
> format for cut/paste.
>
> If we could eliminate the repeated down/up traversals of the
> tree, by using a coroutine approach, for instance, then we could
> reduce cut/paste operations to O(p)---much nicer.  This is what
> I'd like to do.  In such an environment, rle is no longer appropriate
> as an intermediate step because it doesn't respect the two-
> dimensional locality of the pattern; it is only one-dimensionally
> local.  So I'd need to go to a more complex quadtree-type
> intermediate representation, which is definitely doable but
> somewhat complex.
>
> Probably the correct thing to do is to just bite the bullet and
> take all remaining places that are O(n^2 log(u)) and do the
> work to make them O((p+n) log(u)) and call it a day.
>
> (Another somewhat related topic is making cut/paste/etc.
> work for arbitrary areas in huge universes---i.e., get rid of
> the 1B x 1B restriction.  This will add a large constant (or
> worse) factor to the current cut/paste operations if we
> do it in a straightforward way; if we used a quadtree-based
> intermediate representation and traversal, we could get
> the bigint functionality nearly for free, by restricting the
> bigint operations to the high levels of the tree.)
>
> On 12/3/05, Brice <bri...@ve...> wrote:
>> On Sat, 03 Dec 2005 11:56:48 -0500, Tom Rokicki <ro...@gm...>  
>> wrote:
>> > ...it is complicated
>> > by the desire to be able to do rotations and flips and the like (so
>> > the traversal order cannot be predefined).
>>
>> Why not? Traverse the source area in predefined efficient order and
>> execute the setcells() with transformed coordinates. As long as you  
>> don't
>> have to handle the empty areas between sparse cells this use of  
>> setcell()
>> should be plenty fast for anything interactive.
>>
>> I didn't understand the reference to RLE viz. cut and paste. Maybe  
>> you're
>> using an internal clipboard? Does that make sense for mega cut/paste?
>> Where but Golly can you do anything mega? So mega pasting to another
>> program makes little sense. If you need a clipboard for cuts (not  
>> copies),
>> maybe there is a way to utilize the XOR trick to make the cut in place?
>> Like mark the cut area as render-empty but leave the source data in situ
>> until paste. If the paste area overlaps the cut area, then there are  
>> some
>> complications, but if not then you can clear the cut data from the
>> quadtree. I'm sure there is some bitmask magic to handle the overlap.
>>
>> Just thinking out loud in the hopes it'll help you think it through,
>> -brice
>>
>> --
>> Using Opera's revolutionary e-mail client: http://www.opera.com/mail/
>>
>>
>> -------------------------------------------------------
>> This SF.net email is sponsored by: Splunk Inc. Do you grep through log  
>> files
>> for problems?  Stop!  Download the new AJAX search engine that makes
>> searching your log files as easy as surfing the  web.  DOWNLOAD SPLUNK!
>> http://ads.osdn.com/?ad_id=7637&alloc_id=16865&op=click
>> _______________________________________________
>> Golly-test mailing list
>> Gol...@li...
>> https://lists.sourceforge.net/lists/listinfo/golly-test
>>
>
>
> -------------------------------------------------------
> This SF.net email is sponsored by: Splunk Inc. Do you grep through log  
> files
> for problems?  Stop!  Download the new AJAX search engine that makes
> searching your log files as easy as surfing the  web.  DOWNLOAD SPLUNK!
> http://ads.osdn.com/?ad_idv37&alloc_id865&op=click
> _______________________________________________
> Golly-test mailing list
> Gol...@li...
> https://lists.sourceforge.net/lists/listinfo/golly-test



-- 
Using Opera's revolutionary e-mail client: http://www.opera.com/mail/

For the sake of discussion I'm gonna play *really* fast and loose
with complexity theory, but here goes.

Without loss of generalization, let's define n as the width and
height of the cut/paste area, u as the width and height of the
universe, and p as the population of the cut/paste area.

The universe tree in both qlife and hlife is of depth O(log(u)).
Setcell/getcell take time O(log(u)) because they have to walk.
The naive cut/paste that traverses x/y therefore takes time
O(n^2 log(u)).  This is really slow.  Some of the cut/paste-type
operations in golly still take that long.

I implemented a nextcell() routine that returns the next cell
in cartesian order.  Analysis of its runtime is difficult, but
amortized it's probably O(log(u)).  If we use this operation in
cut/paste, and ignoring the cost of clearing the destination
beforehand if necessary, then we can cut down the cut/paste
time to O((p+n)log(u)) (the n is there because nextcell works on
a raster-row by raster-row basis, and a more precise formula
is likely to be O((p+n*log(u))log(u)) but like I said, analysis is
difficult.)  This is still much better than the naive approach, and
it is what we use in several other places in golly.

Both of these methods permit storage of an intermediate
result (a cut) in the RLE format, which itself is roughly
O(p) (but not exactly; a factor describing the average
sparseness of the pattern needs to go in there too).  Since
this doesn't appreciably slow things down, and since RLE
is nice to cut/paste anyway, we use RLE as an intermediate
format for cut/paste.

If we could eliminate the repeated down/up traversals of the
tree, by using a coroutine approach, for instance, then we could
reduce cut/paste operations to O(p)---much nicer.  This is what
I'd like to do.  In such an environment, rle is no longer appropriate
as an intermediate step because it doesn't respect the two-
dimensional locality of the pattern; it is only one-dimensionally
local.  So I'd need to go to a more complex quadtree-type
intermediate representation, which is definitely doable but
somewhat complex.

Probably the correct thing to do is to just bite the bullet and
take all remaining places that are O(n^2 log(u)) and do the
work to make them O((p+n) log(u)) and call it a day.

(Another somewhat related topic is making cut/paste/etc.
work for arbitrary areas in huge universes---i.e., get rid of
the 1B x 1B restriction.  This will add a large constant (or
worse) factor to the current cut/paste operations if we
do it in a straightforward way; if we used a quadtree-based
intermediate representation and traversal, we could get
the bigint functionality nearly for free, by restricting the
bigint operations to the high levels of the tree.)

On 12/3/05, Brice <bri...@ve...> wrote:
> On Sat, 03 Dec 2005 11:56:48 -0500, Tom Rokicki <ro...@gm...> wrote=
:
> > ...it is complicated
> > by the desire to be able to do rotations and flips and the like (so
> > the traversal order cannot be predefined).
>
> Why not? Traverse the source area in predefined efficient order and
> execute the setcells() with transformed coordinates. As long as you don't
> have to handle the empty areas between sparse cells this use of setcell()
> should be plenty fast for anything interactive.
>
> I didn't understand the reference to RLE viz. cut and paste. Maybe you're
> using an internal clipboard? Does that make sense for mega cut/paste?
> Where but Golly can you do anything mega? So mega pasting to another
> program makes little sense. If you need a clipboard for cuts (not copies)=
,
> maybe there is a way to utilize the XOR trick to make the cut in place?
> Like mark the cut area as render-empty but leave the source data in situ
> until paste. If the paste area overlaps the cut area, then there are some
> complications, but if not then you can clear the cut data from the
> quadtree. I'm sure there is some bitmask magic to handle the overlap.
>
> Just thinking out loud in the hopes it'll help you think it through,
> -brice
>
> --
> Using Opera's revolutionary e-mail client: http://www.opera.com/mail/
>
>
> -------------------------------------------------------
> This SF.net email is sponsored by: Splunk Inc. Do you grep through log fi=
les
> for problems?  Stop!  Download the new AJAX search engine that makes
> searching your log files as easy as surfing the  web.  DOWNLOAD SPLUNK!
> http://ads.osdn.com/?ad_id=3D7637&alloc_id=3D16865&op=3Dclick
> _______________________________________________
> Golly-test mailing list
> Gol...@li...
> https://lists.sourceforge.net/lists/listinfo/golly-test
>

On Sat, 03 Dec 2005 11:56:48 -0500, Tom Rokicki <ro...@gm...> wrote:
> ...it is complicated
> by the desire to be able to do rotations and flips and the like (so
> the traversal order cannot be predefined).

Why not? Traverse the source area in predefined efficient order and  
execute the setcells() with transformed coordinates. As long as you don't  
have to handle the empty areas between sparse cells this use of setcell()  
should be plenty fast for anything interactive.

I didn't understand the reference to RLE viz. cut and paste. Maybe you're  
using an internal clipboard? Does that make sense for mega cut/paste?  
Where but Golly can you do anything mega? So mega pasting to another  
program makes little sense. If you need a clipboard for cuts (not copies),  
maybe there is a way to utilize the XOR trick to make the cut in place?  
Like mark the cut area as render-empty but leave the source data in situ  
until paste. If the paste area overlaps the cut area, then there are some  
complications, but if not then you can clear the cut data from the  
quadtree. I'm sure there is some bitmask magic to handle the overlap.

Just thinking out loud in the hopes it'll help you think it through,
-brice

-- 
Using Opera's revolutionary e-mail client: http://www.opera.com/mail/

Hi Tom, Hi Andrew, I know this is a tough problem. You've designed data  
structures that are highly optimized for one particular access pattern and  
also highly optimized to conserve memory. Cut/paste requires totally  
different access patterns -- they just happen to be the worst possible  
cases when compared to the original intent of the structures.

I would suggest stepping back and prioritizing and gathering/guestimating  
statistics for usage patterns. There is no way that mega cut/paste can  
ever be useful as more than a toy. I was simply building large recursive  
structures and letting them self-destruct. A whim. No precision involved.  
Large scale functional patterns will have to be built programmatically.  
And a program building a recursive sponge pattern would be wise to not do  
recursive mega-copy/pastes, but linearize the algorithm. That's just life.

My main concern was exactly that Golly is ultra fast, but *permits* the  
user to attempt a cut/paste operation which stalls for 10s of minutes.  
Duh, the data structures are not designed for this, and why would you want  
to do that anyhow? But you *can*, and the progress bar hack is just  
ebarrassing as it stands.

In practical terms, there is no reason to do a 150k x 50k paste by hand  
except to play. If you made it fast, how often would it get used? It's not  
worth your effort to optimize this unless it can be had almost for free as  
a side effect with some cleverness. I would suggest you modify the  
progress bar to explain to the user the nature of the tradeoff involved.  
Golly is optimized for one thing, and what the user is trying to do  
conflicts and is going to take x minutes, do you really want to do this,  
yes, no? I think the progress bar is the right solution if it provides a  
little more contextual information about why super-fast Golly is suddenly  
a dog. Design tradeoffs have real consequences.

After I asked the render method vs. cut method question I wondered if you  
might be aggregating render hints on the fly during generation. Then  
render code would never have to seek the leaves at large scales. You do,  
so the comparison is void. I was mostly hoping that stripped down render  
code would be more cleaver than nested (x,y) loops, and adapting it would  
be simpler than augmenting the data structures.

My gencols example really doesn't apply anymore. The leaves of your  
quadtrees have no coordinate IDs. So even if you can walk the heap of  
leaves in memory-order, there is no way to find their (x,y) locations  
because (x,y) is only implicit. Cell coordinates seem to be derived solely  
 from the tree walking. But if you did tag the leaves with their quadtree  
address or their (x,y), then you could walk the heap of leaves and simply  
compare with the cut window x+dx, y+dy coords. Quadtree address would be  
more compact, but still large. This kind of out-of-order processing is  
ugly and not optimal, but would extend the cut/paste performance far  
beyond (x,y) loops. The most efficient tag for a leaf node would probably  
be a parent pointer. Coordinate hints could be stored further up in the  
tree. Find a leaf in the heap, follow the parents until you find a  
coordinate hint. It's ugly, but in practice it would be much faster than  
(x,y) scans from the top. And it could be scalable if you allow the  
coordinate hints to be placed at arbitrary levels of the hierarchy.

In the abstract I'm going to guess that there is no practical way to have  
the cake of a fast compact data structure and eat it too with cuts and  
pastes and other far-from-optimal accesses. Either you maintain separate  
parallel indexes or add pointers to the leaf nodes so you can link the  
tree horizontally, or you add (x,y) tags to near-leaf nodes or provide  
coordinate hashing as a second access method, or... but you must in the  
end do one of two things to the data structure: a) bloat the leaves which  
costs big time with huge patterns, or b) spend more time during generation  
to maintain secondary sturctures which costs big time with far-future  
patterns.

Golly was designed to specialize in the far-future and astronomical cases,  
so this kind of "optimizing" just cuts Golly down.

If you do augment the quadtrees for cut/paste, etc, maybe it should be  
temporary, during interactive pattern manipulations. Runtime should go  
back to the dense quadtrees because they're already near-optimal for  
generation.

But don't go killing yourselves with optimization headaches for far-out  
corner-case usages. Like I said, interesting mega patterns will require  
programmatic construction. No one will ever want to assemble a Menger  
sponge of caterpillars by hand. Programs will always be manipulating known  
live cells, not asking Golly to copy huge desolate empty spaces.

As always, just my 2cents.
-brice





On Sat, 03 Dec 2005 11:56:48 -0500, Tom Rokicki <ro...@gm...> wrote:

> Oops, looks like I mispoke.
>
> Some of the copy/paste routines have been sped up but not all.
>
> My goal is to make them all linear in the count of cells.  We're
> not quite there yet.
>
> Rendering can cheat, because when you're zoomed out, you only
> need to know if *any* of a number of pixels are set, not precisely
> which pixels are set.
>
> If you look at the code, you'll see a bunch of places where we
> use nextcell() which returns the nextcell in cartesian order,
> reasonably quickly.  These places should be relatively fast.
> There are other places where we use getcell() in a doubly-nested
> x/y loop; these places are slow.
>
> Long term I was intending to rip all this out and build a pixel-stream
> abstraction that would be fast by doing the treewalk in a pipelined
> fashion, so we don't always have to walk down the tree and back
> up for every set pixel.  But this hasn't happened yet; it is complicated
> by the desire to be able to do rotations and flips and the like (so
> the traversal order cannot be predefined).  To solve this I was thinking
> of simply reflecting the quadtree representation in the cut/paste
> format, but then we're not using a nice clean RLE format anymore.
>
> So I have to admit I'm a bit wedged.  I can, with significant effort,
> make most of the existing slow routines faster---but still slower
> than I would like, and by duplicating a fair amount of code.
> I'd like to get to a better place---less duplication of code, a
> better overall abstraction, and better overall speed---but there are
> too many complications to begin to implement it yet.
>
>
> -------------------------------------------------------
> This SF.net email is sponsored by: Splunk Inc. Do you grep through log  
> files
> for problems?  Stop!  Download the new AJAX search engine that makes
> searching your log files as easy as surfing the  web.  DOWNLOAD SPLUNK!
> http://ads.osdn.com/?ad_idv37&alloc_id865&op=click
> _______________________________________________
> Golly-test mailing list
> Gol...@li...
> https://lists.sourceforge.net/lists/listinfo/golly-test



-- 
Using Opera's revolutionary e-mail client: http://www.opera.com/mail/

Oops, looks like I mispoke.

Some of the copy/paste routines have been sped up but not all.

My goal is to make them all linear in the count of cells.  We're
not quite there yet.

Rendering can cheat, because when you're zoomed out, you only
need to know if *any* of a number of pixels are set, not precisely
which pixels are set.

If you look at the code, you'll see a bunch of places where we
use nextcell() which returns the nextcell in cartesian order,
reasonably quickly.  These places should be relatively fast.
There are other places where we use getcell() in a doubly-nested
x/y loop; these places are slow.

Long term I was intending to rip all this out and build a pixel-stream
abstraction that would be fast by doing the treewalk in a pipelined
fashion, so we don't always have to walk down the tree and back
up for every set pixel.  But this hasn't happened yet; it is complicated
by the desire to be able to do rotations and flips and the like (so
the traversal order cannot be predefined).  To solve this I was thinking
of simply reflecting the quadtree representation in the cut/paste
format, but then we're not using a nice clean RLE format anymore.

So I have to admit I'm a bit wedged.  I can, with significant effort,
make most of the existing slow routines faster---but still slower
than I would like, and by duplicating a fair amount of code.
I'd like to get to a better place---less duplication of code, a
better overall abstraction, and better overall speed---but there are
too many complications to begin to implement it yet.

> Mostly Rhetorical: Why is it that the render methods can access a rectangular region of the universe quickly, but the cut/paste methods can't?

Tom knows more about such things but I think I can help answer this.
The rendering code can take advantage of clipping and scaling info,
but the cut/paste code obviously needs to be accurate at the cell
level regardless of the current scale or viewport location.

Actually, my paste code is quite dumb.  It was written before Tom
provided the nextcell() call which allows much faster scanning of
sparsely populated rects.  There are some obvious cases where I
should use nextcell() to scan the clipboard pattern:

- when using Or mode (should Or be the default instead of Copy?)
- when the current universe is empty
- when the destination rect is outside the current pattern edges

I've made a note to do these optimizations soon, so thanks for
the reminder!  And what the heck are you constructing that requires
cut-and-pastes of 150K x 50K patterns!!  I'm looking forward to
seeing that monster. :)

Brice, if you are looking at the GUI code then I hope you're getting
the latest sources from CVS.  There's been a lot of changes since
the last public release.

Andrew

I have one more question about this, then I'll stop bugging you all until  
I wrap my head tightly around the code.

Mostly Rhetorical: Why is it that the render methods can access a  
rectangular region of the universe quickly, but the cut/paste methods  
can't?

Perhaps the simplest solution is to clone the render methods. Use modifed  
render code to perform cut and paste. The bandwidth problem has obviously  
been solved once already.

-brice

On Sat, 03 Dec 2005 03:05:36 -0500, Brice <bri...@ve...> wrote:

> Hi All, sorry for the prev post being half researched and somewhat  
> wrong. The idea still stands, but some details I got wrong along the way  
> 'cause I relied on my memory and didn't revisit the code. I remembered  
> looking at the particular hash function used in hlife...
>
> Correction: neither hlife nor qlife use a (x,y)->hashtable backing  
> store. Both seem to rely on quadtree concepts.
>
> But my idea still stands conceptually. From a cursory look at the paste  
> methods, they are doing exactly what I guessed: scanning the entire  
> (x,y) coordinate space of the cut area and calling getcell(x,y) on every  
> tuple. For dx=150k and dy=50k this is huge. However the actual number of  
> live cells was 35k, so scanning the low level data structures in  
> memory-order would be much more efficient than scanning the high-level  
> coordinate space. I haven't spent much time following the memory  
> management code; I have no idea if there is some easy way to walk all  
> allocated cells without going through the quadtree indexes. That's  
> what's needed to get rid of the cut/paste bottleneck. Simple access to  
> the set of all low-level cell memory objects -- in any order. That set  
> will almost always be smaller than the full dx*dy cross product of a  
> large cut/paste. In my small-scale example of gencols, this can be had  
> for free by making sure all the cell objects are allocated contiguously.
>
> Anyhow, if I stumble on a solution I'll post. But you all are better  
> programmers than I. So my purpose is mostly to shine a little light on  
> the problem in the hopes that someone will recognize a simple solution.  
> Mega-cut/paste certainly isn't a priority issue. Just a bit embarassing  
> when the fastest life prog ever puts up a progress bar listing a 15+min.  
> ETA to paste a copied area...
>
> Thanks,
> -brice
>
>
>
> On Fri, 02 Dec 2005 22:27:53 -0500, Brice <bri...@ve...> wrote:
>
>> Hi All, I'm sure it is a known problem that pasting very large areas is  
>> unbearably slow -- you have even implemented a progress meter and  
>> cancel button. I was pasting an area 150k x 50k while the universe pop  
>> totaled 35k cells. Progress meter said >15min. so I said Cancel. Both  
>> hlife and qlife modes are similar.
>>
>> I have a 2cent idea about this. I have been rewriting / merging gencols  
>> and Hensel's applet codes. (But I have not plowed through the Golly UI  
>> code yet.)
>>
>> Guess: the problem is caused by the backend hash table scheme used to  
>> index (x,y) coordinate tuples. Gencols does this too. From the slowness  
>> of paste I'm guessing you are scanning the entire (x,y) coordinate  
>> space of the cut area and doing a hash table querry for every tuple.  
>> Gencols does this often. But not for very large areas which are very  
>> sparsely populated...
>>
>> Idea: is there a simple way to walk the "heap" of cell objects in  
>> memory-order (out of cartesian-order)? I.e. bypass the  
>> (x,y)->hash->object lookup? For (universe populations) << (grid cells  
>> in paste area) it will be much more efficient to scan all  
>> live/allocated cells out of order and compare their coordinates to the  
>> cut window. Rather than scanning the cut window coordinate space and  
>> querrying the table for live cells. High density pops would still be  
>> penalized with slow pastes, but nearly all large area cut/paste would  
>> be with sparse patterns I think.
>>
>> I understand that memory allocation fragmentation could make this  
>> non-trivial. For my gencols rewrite I am pre-allocating arrays of cell  
>> objects so they can be walked as a contig... but without the overhead  
>> of maintaining a linked list of live cells. Chunking and chaining bulk  
>> pre-allocations may not fit the Golly model right now. A wacky idea: it  
>> could be possible to crudely scan the entire application heap and look  
>> for cell object signatures -- decode putative (x,y) and verify with the  
>> hash table. The total possible real+bogus objects would still be <<  
>> (150*50)k for example. Then you wouldn't have to track de/pre/allocated  
>> cells tightly. Use such an ugly hack when cut area >> universe pop.
>>
>> Sorry I don't have code to contribute.
>>
>> -brice
>>
>>
>> Using Opera's revolutionary e-mail client: http://www.opera.com/mail/
>>
>>
>> -------------------------------------------------------
>> This SF.net email is sponsored by: Splunk Inc. Do you grep through log  
>> files
>> for problems?  Stop!  Download the new AJAX search engine that makes
>> searching your log files as easy as surfing the  web.  DOWNLOAD SPLUNK!
>> http://ads.osdn.com/?ad_id=7637&alloc_id=16865&op=click
>> _______________________________________________
>> Golly-test mailing list
>> Gol...@li...
>> https://lists.sourceforge.net/lists/listinfo/golly-test
>
>
>



-- 
Using Opera's revolutionary e-mail client: http://www.opera.com/mail/

We're preparing a new release that I believe will largely address your
concerns.

Things are not as fast as I would like, but for both hlife and qlife
the version in testing now should be far better.

-tom

On 12/3/05, Brice <bri...@ve...> wrote:
> Hi All, sorry for the prev post being half researched and somewhat wrong.
> The idea still stands, but some details I got wrong along the way 'cause =
I
> relied on my memory and didn't revisit the code. I remembered looking at
> the particular hash function used in hlife...
>
> Correction: neither hlife nor qlife use a (x,y)->hashtable backing store.
> Both seem to rely on quadtree concepts.
>
> But my idea still stands conceptually. From a cursory look at the paste
> methods, they are doing exactly what I guessed: scanning the entire (x,y)
> coordinate space of the cut area and calling getcell(x,y) on every tuple.
> For dx=3D150k and dy=3D50k this is huge. However the actual number of liv=
e
> cells was 35k, so scanning the low level data structures in memory-order
> would be much more efficient than scanning the high-level coordinate
> space. I haven't spent much time following the memory management code; I
> have no idea if there is some easy way to walk all allocated cells withou=
t
> going through the quadtree indexes. That's what's needed to get rid of th=
e
> cut/paste bottleneck. Simple access to the set of all low-level cell
> memory objects -- in any order. That set will almost always be smaller
> than the full dx*dy cross product of a large cut/paste. In my small-scale
> example of gencols, this can be had for free by making sure all the cell
> objects are allocated contiguously.
>
> Anyhow, if I stumble on a solution I'll post. But you all are better
> programmers than I. So my purpose is mostly to shine a little light on th=
e
> problem in the hopes that someone will recognize a simple solution.
> Mega-cut/paste certainly isn't a priority issue. Just a bit embarassing
> when the fastest life prog ever puts up a progress bar listing a 15+min.
> ETA to paste a copied area...
>
> Thanks,
> -brice
>
>
>
> On Fri, 02 Dec 2005 22:27:53 -0500, Brice <bri...@ve...> wrote:
>
> > Hi All, I'm sure it is a known problem that pasting very large areas is
> > unbearably slow -- you have even implemented a progress meter and cance=
l
> > button. I was pasting an area 150k x 50k while the universe pop totaled
> > 35k cells. Progress meter said >15min. so I said Cancel. Both hlife and
> > qlife modes are similar.
> >
> > I have a 2cent idea about this. I have been rewriting / merging gencols
> > and Hensel's applet codes. (But I have not plowed through the Golly UI
> > code yet.)
> >
> > Guess: the problem is caused by the backend hash table scheme used to
> > index (x,y) coordinate tuples. Gencols does this too. From the slowness
> > of paste I'm guessing you are scanning the entire (x,y) coordinate spac=
e
> > of the cut area and doing a hash table querry for every tuple. Gencols
> > does this often. But not for very large areas which are very sparsely
> > populated...
> >
> > Idea: is there a simple way to walk the "heap" of cell objects in
> > memory-order (out of cartesian-order)? I.e. bypass the
> > (x,y)->hash->object lookup? For (universe populations) << (grid cells i=
n
> > paste area) it will be much more efficient to scan all live/allocated
> > cells out of order and compare their coordinates to the cut window.
> > Rather than scanning the cut window coordinate space and querrying the
> > table for live cells. High density pops would still be penalized with
> > slow pastes, but nearly all large area cut/paste would be with sparse
> > patterns I think.
> >
> > I understand that memory allocation fragmentation could make this
> > non-trivial. For my gencols rewrite I am pre-allocating arrays of cell
> > objects so they can be walked as a contig... but without the overhead o=
f
> > maintaining a linked list of live cells. Chunking and chaining bulk
> > pre-allocations may not fit the Golly model right now. A wacky idea: it
> > could be possible to crudely scan the entire application heap and look
> > for cell object signatures -- decode putative (x,y) and verify with the
> > hash table. The total possible real+bogus objects would still be <<
> > (150*50)k for example. Then you wouldn't have to track de/pre/allocated
> > cells tightly. Use such an ugly hack when cut area >> universe pop.
> >
> > Sorry I don't have code to contribute.
> >
> > -brice
> >
> >
> > Using Opera's revolutionary e-mail client: http://www.opera.com/mail/
> >
> >
> > -------------------------------------------------------
> > This SF.net email is sponsored by: Splunk Inc. Do you grep through log
> > files
> > for problems?  Stop!  Download the new AJAX search engine that makes
> > searching your log files as easy as surfing the  web.  DOWNLOAD SPLUNK!
> > http://ads.osdn.com/?ad_id=3D7637&alloc_id=3D16865&op=3Dclick
> > _______________________________________________
> > Golly-test mailing list
> > Gol...@li...
> > https://lists.sourceforge.net/lists/listinfo/golly-test
>
>
>
> --
> Using Opera's revolutionary e-mail client: http://www.opera.com/mail/
>
>
> -------------------------------------------------------
> This SF.net email is sponsored by: Splunk Inc. Do you grep through log fi=
les
> for problems?  Stop!  Download the new AJAX search engine that makes
> searching your log files as easy as surfing the  web.  DOWNLOAD SPLUNK!
> http://ads.osdn.com/?ad_id=3D7637&alloc_id=3D16865&op=3Dclick
> _______________________________________________
> Golly-test mailing list
> Gol...@li...
> https://lists.sourceforge.net/lists/listinfo/golly-test
>

Hi All, sorry for the prev post being half researched and somewhat wrong.  
The idea still stands, but some details I got wrong along the way 'cause I  
relied on my memory and didn't revisit the code. I remembered looking at  
the particular hash function used in hlife...

Correction: neither hlife nor qlife use a (x,y)->hashtable backing store.  
Both seem to rely on quadtree concepts.

But my idea still stands conceptually. From a cursory look at the paste  
methods, they are doing exactly what I guessed: scanning the entire (x,y)  
coordinate space of the cut area and calling getcell(x,y) on every tuple.  
For dx=150k and dy=50k this is huge. However the actual number of live  
cells was 35k, so scanning the low level data structures in memory-order  
would be much more efficient than scanning the high-level coordinate  
space. I haven't spent much time following the memory management code; I  
have no idea if there is some easy way to walk all allocated cells without  
going through the quadtree indexes. That's what's needed to get rid of the  
cut/paste bottleneck. Simple access to the set of all low-level cell  
memory objects -- in any order. That set will almost always be smaller  
than the full dx*dy cross product of a large cut/paste. In my small-scale  
example of gencols, this can be had for free by making sure all the cell  
objects are allocated contiguously.

Anyhow, if I stumble on a solution I'll post. But you all are better  
programmers than I. So my purpose is mostly to shine a little light on the  
problem in the hopes that someone will recognize a simple solution.  
Mega-cut/paste certainly isn't a priority issue. Just a bit embarassing  
when the fastest life prog ever puts up a progress bar listing a 15+min.  
ETA to paste a copied area...

Thanks,
-brice



On Fri, 02 Dec 2005 22:27:53 -0500, Brice <bri...@ve...> wrote:

> Hi All, I'm sure it is a known problem that pasting very large areas is  
> unbearably slow -- you have even implemented a progress meter and cancel  
> button. I was pasting an area 150k x 50k while the universe pop totaled  
> 35k cells. Progress meter said >15min. so I said Cancel. Both hlife and  
> qlife modes are similar.
>
> I have a 2cent idea about this. I have been rewriting / merging gencols  
> and Hensel's applet codes. (But I have not plowed through the Golly UI  
> code yet.)
>
> Guess: the problem is caused by the backend hash table scheme used to  
> index (x,y) coordinate tuples. Gencols does this too. From the slowness  
> of paste I'm guessing you are scanning the entire (x,y) coordinate space  
> of the cut area and doing a hash table querry for every tuple. Gencols  
> does this often. But not for very large areas which are very sparsely  
> populated...
>
> Idea: is there a simple way to walk the "heap" of cell objects in  
> memory-order (out of cartesian-order)? I.e. bypass the  
> (x,y)->hash->object lookup? For (universe populations) << (grid cells in  
> paste area) it will be much more efficient to scan all live/allocated  
> cells out of order and compare their coordinates to the cut window.  
> Rather than scanning the cut window coordinate space and querrying the  
> table for live cells. High density pops would still be penalized with  
> slow pastes, but nearly all large area cut/paste would be with sparse  
> patterns I think.
>
> I understand that memory allocation fragmentation could make this  
> non-trivial. For my gencols rewrite I am pre-allocating arrays of cell  
> objects so they can be walked as a contig... but without the overhead of  
> maintaining a linked list of live cells. Chunking and chaining bulk  
> pre-allocations may not fit the Golly model right now. A wacky idea: it  
> could be possible to crudely scan the entire application heap and look  
> for cell object signatures -- decode putative (x,y) and verify with the  
> hash table. The total possible real+bogus objects would still be <<  
> (150*50)k for example. Then you wouldn't have to track de/pre/allocated  
> cells tightly. Use such an ugly hack when cut area >> universe pop.
>
> Sorry I don't have code to contribute.
>
> -brice
>
>
> Using Opera's revolutionary e-mail client: http://www.opera.com/mail/
>
>
> -------------------------------------------------------
> This SF.net email is sponsored by: Splunk Inc. Do you grep through log  
> files
> for problems?  Stop!  Download the new AJAX search engine that makes
> searching your log files as easy as surfing the  web.  DOWNLOAD SPLUNK!
> http://ads.osdn.com/?ad_id=7637&alloc_id=16865&op=click
> _______________________________________________
> Golly-test mailing list
> Gol...@li...
> https://lists.sourceforge.net/lists/listinfo/golly-test



-- 
Using Opera's revolutionary e-mail client: http://www.opera.com/mail/

Hi All, I'm sure it is a known problem that pasting very large areas is  
unbearably slow -- you have even implemented a progress meter and cancel  
button. I was pasting an area 150k x 50k while the universe pop totaled  
35k cells. Progress meter said >15min. so I said Cancel. Both hlife and  
qlife modes are similar.

I have a 2cent idea about this. I have been rewriting / merging gencols  
and Hensel's applet codes. (But I have not plowed through the Golly UI  
code yet.)

Guess: the problem is caused by the backend hash table scheme used to  
index (x,y) coordinate tuples. Gencols does this too. From the slowness of  
paste I'm guessing you are scanning the entire (x,y) coordinate space of  
the cut area and doing a hash table querry for every tuple. Gencols does  
this often. But not for very large areas which are very sparsely  
populated...

Idea: is there a simple way to walk the "heap" of cell objects in  
memory-order (out of cartesian-order)? I.e. bypass the (x,y)->hash->object  
lookup? For (universe populations) << (grid cells in paste area) it will  
be much more efficient to scan all live/allocated cells out of order and  
compare their coordinates to the cut window. Rather than scanning the cut  
window coordinate space and querrying the table for live cells. High  
density pops would still be penalized with slow pastes, but nearly all  
large area cut/paste would be with sparse patterns I think.

I understand that memory allocation fragmentation could make this  
non-trivial. For my gencols rewrite I am pre-allocating arrays of cell  
objects so they can be walked as a contig... but without the overhead of  
maintaining a linked list of live cells. Chunking and chaining bulk  
pre-allocations may not fit the Golly model right now. A wacky idea: it  
could be possible to crudely scan the entire application heap and look for  
cell object signatures -- decode putative (x,y) and verify with the hash  
table. The total possible real+bogus objects would still be << (150*50)k  
for example. Then you wouldn't have to track de/pre/allocated cells  
tightly. Use such an ugly hack when cut area >> universe pop.

Sorry I don't have code to contribute.

-brice


Using Opera's revolutionary e-mail client: http://www.opera.com/mail/