apgsearch v1.0

[Alexey_Nigin]

That's okay. The xp2 tabulation (which is by far the largest) is only 140K in size, which means it can grow to about 7 times its current size (or 40K distinct objects) before Catagolue breaks.

What will happen if the size of an entry actually reaches 1MB?

By the way, I noticed that you have raised the requirements on statistics page, and it is still quite large. I am amazed by the rate at which object count in B3/S23 C1 is growing.

[dvgrn]

That's okay. The xp2 tabulation (which is by far the largest) is only 140K in size, which means it can grow to about 7 times its current size (or 40K distinct objects) before Catagolue breaks.

What will happen if the size of an entry actually reaches 1MB?

And is there a way to make a decent estimate of how many soups will have to be processed before the xp2 tabulation reaches 1MB? Are we seeing new p2 oscillators appearing at a more or less linear rate these days? Or is the rate decreasing as we run out of likely p2 objects -- maybe some kind of logarithmic decline?

The last estimate I can remember is from an email back in February:

"... the limiting factor of Catagolue growth (that each tabulation can only be at most one megabyte) should only start to kick in once we've amassed a few tens of thousands of still-lifes of the same population count for one ordered pair of the form (rule, symmetry). This will probably happen after processing around 10^13 soups for that particular ordered pair (equivalent to about 100 Lifenthusiasts running apgsearch continually for an entire year, focusing only on one ordered pair, which seems incredibly optimistic)."

We're already only a couple of orders of magnitude away from 10^13 soups for b3s23/C1, and the End of Time doesn't seem any nigher than usual, so maybe the moral here is not to underestimate Lifenthusiasts.

But maybe we also have enough data for a better estimate of for the first overflow, now? And it seems as if there must be fairly simple workarounds, anyway, including "fix the mysterious misidentification bug and restart the counts..."

Somewhat tangentially: I just noticed today, from looking up Zipf's Law on Wikipedia, that there might be a reason for the two distinct slopes visible in Achim's log-log graph of frequency versus rank. Different parts of the curve might fit different parametrizations of Mandelbrot's generalization of Zipf's Law.

Anyone who knows more about power-law statistics than I do (it wouldn't be hard, really)... might this make some kind of sense, or am I misreading something?

[Alexey_Nigin]

I have made a package which contains everything you need to run apgsearch on 64-bit Windows. apgsearch is slightly hacked, so you do not need to enter rule, symmetry, etc. each time. Includes BAT files which can be put into your Startup folder. Uses version of apgsearch from a few days ago. More detailed information is contained within ReadMe.txt.

https://yadi.sk/d/oERi1Im2gZSZ5

Edit: it uses not-too-stable version of apgsearch. Also an apostrophe in "Nigin's Public Account" is causing trouble. Check out a new version here:

https://yadi.sk/d/PgFXRrYJgbDKY

[biggiemac]

I upgraded 92 C1 instances to the new 1.04 version. I also have 11 instances still on 1.03, I'll upgrade them once the computers on which they're running are not in use by frosh hammering through final papers.

I started a handful (7) instances in D4_x4. Any idea why it runs faster there? (430 soups/sec instead of 315 on my computers?)

Never underestimate life enthusiasts might be a good moral here

[Rocknlol]

How difficult would it be to implement support for B0/D8 rules? I'd imagine it would be fairly complicated given the requirements but I haven't looked through the code enough to know to what extent.

[Andrew]

I started a handful (7) instances in D4_x4.

You might also consider throwing some CPUs at D8_1 and D8_4. I recently created a version of apgsearch to compare the performance of the different symmetries, not only in how fast they run but how good they are at finding unique objects. The C1 search is poor in both categories:

Code: Select all

sym     [# of unique objects at   soups/sec
         10^2 ... 10^6 soups]
C1      [17, 25, 44,  80, 188]    288
8x32    [20, 28, 42,  75, 180]    266
C2_1    [13, 24, 52,  97, 221]    242
C2_2    [18, 30, 47,  90, 197]    239
C2_4    [16, 23, 41,  88, 186]    241
C4_1    [13, 19, 40,  83, 193]    260
C4_4    [13, 21, 41,  79, 168]    250
D2_+1   [17, 32, 55,  96, 253]    341
D2_+2   [12, 27, 46,  88, 203]    333
D2_x    [16, 28, 56, 102, 276]    585
D4_+1   [18, 27, 52, 125, 297]    316
D4_+2   [18, 28, 50, 112, 305]    328
D4_+4   [13, 25, 40,  76, 182]    335
D4_x1   [17, 35, 66, 151, 347]    418
D4_x4   [19, 35, 70, 146, 372]    400
D8_1    [13, 39, 90, 192, 512]    421
D8_4    [16, 30, 62, 125, 329]    455

[biggiemac]

An overwhelming majority of the unique objects in horizontal-flip-symmetric soups are just large still lives. A quick click in D8_1 xs136 (a pseudorandomly selected still life category) identifies 248 unique objects at that bit count alone. I'm not sure that number-of-unique-objects is a particularly useful metric.
D2_x runs the fastest by that wide of a margin? Curious.

[Andrew]

I'm not sure that number-of-unique-objects is a particularly useful metric.

I wouldn't discount those symmetric searches too quickly. They've found a number of prime-period oscillators (xp11, xp29, xp37) that gives me slight hope one of the missing periods might pop out one day.

EDIT: And a D4_+2 search just found the 1st example of a period-31 oscillator:
http://catagolue.appspot.com/object/xp3 ... y066/b3s23

[Andrew]

An overwhelming majority of the unique objects in horizontal-flip-symmetric soups are just large still lives.

It's also true that an overwhelming majority of the unique objects in asymmetric soups are just small still lives. The following table lists object prefixes and their counts across all b3s23 searches:

Code: Select all

xs4 : 2
xs5 : 1
xs6 : 5
xs7 : 4
xs8 : 9
xs9 : 10
xs10 : 25
xs11 : 46
xs12 : 121
xs13 : 234
xs14 : 526
xs15 : 821
xs16 : 1242
xs17 : 1629
xs18 : 1967
xs19 : 2015
xs20 : 2220
xs21 : 1836
xs22 : 1992
xs23 : 1207
xs24 : 1583
xs25 : 657
xs26 : 1415
xs27 : 394
xs28 : 1411
xs29 : 251
xs30 : 1379
xs31 : 188
xs32 : 1270
xs33 : 144
xs34 : 974
xs35 : 86
xs36 : 942
xs37 : 59
xs38 : 597
xs39 : 41
xs40 : 636
xs41 : 15
xs42 : 312
xs43 : 14
xs44 : 507
xs45 : 8
xs46 : 174
xs47 : 2
xs48 : 386
xs49 : 2
xs50 : 81
xs51 : 2
xs52 : 340
xs53 : 1
xs54 : 48
xs56 : 304
xs58 : 36
xs60 : 261
xs62 : 20
xs64 : 285
xs66 : 8
xs68 : 297
xs70 : 4
xs72 : 351
xs74 : 1
xs76 : 332
xs78 : 2
xs80 : 488
xs82 : 2
xs84 : 378
xs86 : 1
xs88 : 545
xs92 : 296
xs96 : 589
xs100 : 290
xs104 : 561
xs108 : 234
xs112 : 502
xs116 : 152
xs120 : 446
xs124 : 107
xs128 : 335
xs132 : 65
xs136 : 267
xs140 : 42
xs144 : 165
xs148 : 24
xs152 : 122
xs156 : 9
xs160 : 90
xs164 : 6
xs168 : 55
xs172 : 3
xs176 : 29
xs180 : 3
xs184 : 16
xs188 : 2
xs192 : 9
xs200 : 5
xs208 : 1
xs224 : 1
xs232 : 1

xp2 : 3890
xp3 : 351
xp4 : 71
xp5 : 92
xp6 : 34
xp8 : 15
xp9 : 1
xp10 : 5
xp11 : 1
xp14 : 1
xp15 : 98
xp16 : 2
xp24 : 4
xp28 : 1
xp29 : 1
xp30 : 33
xp31 : 1
xp37 : 1
xp46 : 2
xp51 : 1
xp120 : 3
xp138 : 1

xq4 : 15
xq12 : 2

yl12 : 1
yl78 : 1
yl120 : 1
yl144 : 1
yl180 : 1
yl288 : 2
yl384 : 59
yl480 : 2
yl576 : 2
yl768 : 2
yl1152 : 1
yl1344 : 1

There are 2 clear peaks for xs objects: one around xs20 (mostly found by the C1 search) and another somewhere around xs112 (mostly found by the symmetric searches). I'm guessing the main reason for the 2 peaks is related to the soup size; ie. C1 soups are 16x16 and the symmetric searches are around 32x32.

[biggiemac]

Were 5 hauls dropped? It currently says 10 uncomitted hauls and only shows 5..

I used the golly-start.py approach to make starting the instances easier and they all are uploading 9M at a time - as a result they are all uploading them at the same time. I hope that doesn't choke the server..

Edit: The disparity (# "uncomitted" - #shown in uncomitted list) has now grown to 13. I think it has been strictly increasing.

Edit: 14. And now the tide has passed, so the 14 uncommitted hauls are persisting through each cron because the server finds nothing to commit. Hope this gets addressed, because that's 126M soups.

[Billabob]

Minor bug: The link to Period-4 oscillators actually leads to the Period-3 page.

[apg]

Edit: 14. And now the tide has passed, so the 14 uncommitted hauls are persisting through each cron because the server finds nothing to commit. Hope this gets addressed, because that's 126M soups.

This is a known concurrency bug, which has only occurred once in the past to my knowledge. If my understanding of the bug is correct (that it's caused by uploading a haul during a cron), then the following will apply:

Good news: The hauls have still been committed, so all of the tabulations and sample soups have been correctly updated.

Bad news: The two counters showing the total number of soups and the total number of objects haven't updated correctly, nor has the list of high-scoring soups. Of course, the actual total number of objects can be deduced from summing the 'occurrences' column of textcensus, and the total number of soups can be estimated by rescaling appropriately.

Anyway, I've now implemented a workaround, namely that uploading a haul only changes the Census entity when there are no other uncommitted hauls. This means that there won't be lots of concurrent writes to the same Census entity, and during a barrage would only occur immediately after a cron has completed, so we should be fine. As a side-effect, the exact number of uncommitted hauls won't be tracked (instead being just a boolean to indicate whether or not there are uncommitted hauls).

I started a handful (7) instances in D4_x4. Any idea why it runs faster there? (430 soups/sec instead of 315 on my computers?)

I imagine C1 soups take longer to stabilise. (Both symmetries seem to produce similar numbers of objects: 21.8427 for C1 and 20.5907 for D4_x4.)

And is there a way to make a decent estimate of how many soups will have to be processed before the xp2 tabulation reaches 1MB?

Just to reiterate: this is for Day and Night, by the way; the b3s23/C1 tabulations are far behind. It should only take about 20 million soups or so in Day and Night to reach 1MB.

What will happen if the size of an entry actually reaches 1MB?

Everything breaks! I'll let you know when I've put in place some workaround to deal with this.

[apg]

I'll let you know when I've put in place some workaround to deal with this.

Now it no longer breaks, but rather only keeps track of the N most common objects of a particular prefix, where N is the largest value such that the the tabulation size is below 980K. This is sufficient, for example, to record all 45759 19-bitters (which should take about 923K).

I'm now DDoSing Catagolue with Day and Night soups to test its scalability for large tabulations.

[dvgrn]

There are 2 clear peaks for xs objects: one around xs20 (mostly found by the C1 search) and another somewhere around xs112 (mostly found by the symmetric searches). I'm guessing the main reason for the 2 peaks is related to the soup size; ie. C1 soups are 16x16 and the symmetric searches are around 32x32.

I was looking at this yesterday for a little while. The statistics page shows the first peak as being at xs19. It seems to me that this peak must be creeping upward gradually over time. The left side of the graph is strictly bounded by the number of distinct still lifes available, whereas farther to the right it gets progressively rarer to see N-bit still lifes, but there are a lot more of them to choose from... so when we see one it's probably new and not a duplicate, pushing the peak a little bit to the right.

I'm guessing the main reason for the 2 peaks is related to the soup size; ie. C1 soups are 16x16 and the symmetric searches are around 32x32.

Well, it doesn't seem likely that a 32x32 C1 soup-search run would turn up all that many more high-bit-count objects. It would just be proportional to the average size of the resulting ash, I suppose, which would certainly be somewhat larger for a 32x32 soup than for 16x16, but that shouldn't be enough to cause such a large effect.

Even doubling the soup size again to 64x64 might not move the second peak very far upward. There would be some increase, no doubt, but subject to diminishing returns.

The large objects are pretty much invariably symmetric forms delicately balanced around the center of symmetry, and they're almost all smaller than 32x32 (right?). A quick review of D8_4 turned up one still life bigger than 32x32, so it does happen occasionally.

My short summary would be that no matter how large a symmetric soup gets, it still has only one center of symmetry, and that's where the big objects are mostly going to show up. And C1 soups will never be able to compete with symmetric soups no matter how big they get, because they don't have that center of symmetry.

[apg]

I'm now DDoSing Catagolue with Day and Night soups to test its scalability for large tabulations.

Scalability is fine, so b3s23/C1 should last as long as I decreed. However, the load at the moment due to Alexey Nigin's three-core attack is stealing so much time that the cron job is ignoring the other censuses (I implemented safety features to prevent DeadlineExceededExceptions occurring during critical operations).

[biggiemac]

I was about to ask why C1 was ignored at the most recent 15-minute mark, glad that's explainable. Also, do you have any explanation for the 72-point C1 soup that only makes 3 LWSS and a pentadecathlon?

[Alexey_Nigin]

Adam, when you said that non-Day-and-Night censuses were ignored, what exactly did you mean? Were the hauls permanently deleted? Or were they just being committed later than usual? Also, didn't my attack cost you money?

I have stopped my attack and will not restart it unless I get relieving answers.

[apg]

We're nearing the 2-teraobject mark for b3s23/C1, and only missing 7 of the 240 thirteen-bit objects. We've already overtaken 4 times the size of Okrasinski's search.

HORIZONTAL LINE

Good news: The xp2 tabulation of b3678s34678/C1 has stopped at a size of 980016 bytes, precisely as I intended. This means that Catagolue won't break whenever large numbers of unique objects are tabulated. Instead, anything rarer than the top 980 kilobytes of objects of that type will be ignored.

Calling /textcensus for Day and Night takes <3 seconds to return the full list of 62599 distinct objects, which is reasonably rapid. The /statistics page essentially performs the same retrieval operation, so will still load relatively quickly even when b3s23/C1 reaches 10^13 objects.

This concludes my scalability test.

HORIZONTAL LINE

Adam, when you said that non-Day-and-Night censuses were ignored, what exactly did you mean? Were the hauls permanently deleted? Or were they just being committed later than usual?

No, the hauls aren't deleted. It's just that the cron task doesn't have enough time to process the other rules, so it waits until the next time the cron task is called (which again might run out of time if there are more Day and Night hauls, postponing things even longer). But now you've stopped the attack, the next call will commit everything that's left over -- and indeed it has done.

I have stopped my attack and will not restart it unless I get relieving answers.

If you restart it, then everything else will grind to a halt again, so I would prefer it if you didn't have three CPUs running Day and Night simultaneously. You might be able to get away with one or two, but three is too much.

(This is a huge contrast to b3s23/C1, where Catagolue can support the combined onslaught of hundreds of CPUs quite easily.)

Also, didn't my attack cost you money?

Only a few cents.

HORIZONTAL LINE

Also, do you have any explanation for the 72-point C1 soup that only makes 3 LWSS and a pentadecathlon?

Well it should be 36 points, which suggests that the scores weren't properly reset after an error-correcting phase and therefore counted again. But I have no idea how that could possibly happen, since the following lines clearly exist:

Code: Select all

                # Reset the object counts:
                self.objectcounts = prevdict
                self.soupscores = prevscores
                self.superunids = prevunids

Maybe someone was using a bootleg version of apgsearch with these lines commented out? Fortunately, we can see precisely who the perpetrator is:

"http://catagolue.appspot.com/hashsoup/C ... vVUePXvzus[/b]7934054/b3s23"

MD5 hash of HNvVUePXvzus is 0ee171d2f71e97f2f0b8a6d8f384214d.

http://catagolue.appspot.com/haul/b3s23 ... d8f384214d

"This haul was submitted by bwbigmac@[...] on 2015-05-12 at 14:22:28 UTC. It contains 196534513 objects generated from 9000000 soups."

So, have you been messing with the script (possibly to improve performance) or not?

[Alexey_Nigin]

• I have now got one instance investigating DN, while other two are exploring close Life variants.
• My tries to persuade other people to download apgsearch are not too successful. Vasiliy Neckrasov is occasionally uploading hauls, Andrey Mikryukov will start donating two cores tomorrow and two or three more cores later, and other people do not seem to respond.
• What is the difference between the version from 05-04 and the current one?

[biggiemac]

Also, do you have any explanation for the 72-point C1 soup that only makes 3 LWSS and a pentadecathlon?

Well it should be 36 points, which suggests that the scores weren't properly reset after an error-correcting phase and therefore counted again. But I have no idea how that could possibly happen, since the following lines clearly exist:

Code: Select all

                # Reset the object counts:
                self.objectcounts = prevdict
                self.soupscores = prevscores
                self.superunids = prevunids

Maybe someone was using a bootleg version of apgsearch with these lines commented out? Fortunately, we can see precisely who the perpetrator is:

"http://catagolue.appspot.com/hashsoup/C ... vVUePXvzus[/b]7934054/b3s23"

MD5 hash of HNvVUePXvzus is 0ee171d2f71e97f2f0b8a6d8f384214d.

http://catagolue.appspot.com/haul/b3s23 ... d8f384214d

"This haul was submitted by bwbigmac@[...] on 2015-05-12 at 14:22:28 UTC. It contains 196534513 objects generated from 9000000 soups."

So, have you been messing with the script (possibly to improve performance) or not?

I can assure you, despite my reputation, I didn't alter the script running my current 9M soup/haul instances except to hardcode the GUI inputs and call the thing golly-start.py. Those lines are indeed present in the shared file. Some freak cosmic ray event, perhaps?

[Alexey_Nigin]

DN hauls from an hour ago are still not committed. Why?

Edit:

Ouch! All arriving hauls are not being committed, even b3s23/C1 ones!

[Extrementhusiast]

DN hauls from an hour ago are still not committed. Why?

Edit:

Ouch! All arriving hauls are not being committed, even b3s23/C1 ones!

Stop all DN searches, and see if that helps.

~

On a different note, any chance of being able to sort objects by the time of the most recent soup added to the Catagolue? (For instance, the mirrored dock would be all the way at the back, as there would be no soups added recently, as there are already a sufficient number of sample soups.)

If not that, can there at least be a "Skip to page" option, so we don't have to load every page in between?

[apg]

Ouch! All arriving hauls are not being committed, even b3s23/C1 ones!

I don't know why this is happening. Maybe Google's servers are lagging more than usual. Anyway, I've now told Catagolue to not process any Day and Night censuses (since they're taking too long) and everything seems to function properly.

If not that, can there at least be a "Skip to page" option, so we don't have to load every page in between?

You mean like:

Code: Select all

http://catagolue.appspot.com/census/b3s23/C1/xs20?offset=200

where '200' is an arbitrary positive integer?

What is the difference between the version from 05-04 and the current one?

The version from -05-04 was a personal performance test (the quickest way to transfer it from my laptop to the cloud was to just tacitly upload it; sorry about that!) and is less stable than the actual release (namely -05-09).

[apg]

Update: I've now re-enabled processing of Day and Night soups. The main problem was the O(n^2) latency of repeated string concatenation, which has now been reduced to O(n) by using StringBuilder.append() instead of using the += operator on strings.

(Thanks for load-testing Catagolue with Day and Night soups, by the way; this has helped non-Borelly* in deciding which parts of the code to optimise.)

* the adjective to use whenever 'immeasurably' seems slightly too strong.

[biggiemac]

Some freak cosmic ray event, perhaps?

It happened again, a pulsar + clock + Block-laying-switch-engine soup worth 40 points clocked in at 80. What might be doing this?