Big O optimisation in mutation storage

[ikke]

I haven't looked at the code in DB2 but by the looks of it (memory consumption, speed of speciation algorithm) mutations are stored as an array per bot. This results in n(bots)* m(mutations) as the big O
If mutations are stored in a tree of life structure this number goes down, and sifting through mutation info takes less space and goes faster. Worst case (no common ancestor of the bots) the number is up to (n+1)*m ((n+1) because for every series of mutations I want to store the number of individuals with those mutations.) The storage becomes increasingly efficient as more bots share al larger common ancestry. In addition to increased performance all sorts of nice graphs and stats can be made.

Definitions
branch: a series of mutations separated in time shared by a number of bots (n>=0, 0 meaning that the branch is now extinct)
node: endpoint of a branch. Branches may link at nodes, referring to an older branch
Every mutation either expands a branch or creates a new branch on a node.
The mutations a bot has inherited or accumulated can now be defined as a reference to the branch structure.
If a bot is born, the population count of the branches in the branch structure in increased. Similarly it is decreased if a bot dies.
Branches may be merged if the older and newer branch have the same population count. Branches where the population count has decreased to 0 may be pruned (deleted or stored off line)

With all that has been said about the first version not being optimised, I just would like to put it up here as an idea, to keep in mind, and hopefully not to put too much effort in work that would be erdone if this would be implemented.

[Numsgil]

That's what I'm going to do, yeah.  I would have changed it to something like an ancestry tree a long time ago but building complex data structures in VB6 wasn't easy at all.  With any luck I should be able to associate the mutation details to the actual DNA like metadata, so after a number of sexual crossover events, etc. you still end up with useful information.  You can examine the individual ancestry of a single gene even.  Or single condition.

I'd also like to figure out a DNA "optimizing compiler" at some point.  So given a bunch of evolved, random DNA it'll prune out any junk DNA and combine constants, etc. to produce not only more readable DNA but shorter DNA so it would be faster to execute.  And then do analysis on it to detect which sysvars it actually reads to/from, and for bots that share the same DNA, and happen to have the same values for the read from sysvars, you can execute the DNA just once and update all the bots at the same time in a giant batch.

Probably less useful for leagues and such, but for zerobot sims it means execution time can drop significantly per cycle.  If all bots' DNA compiles down to nothing, because it's all 0s, I can just literally skip it.

[jknilinux]

Will there be an optimizer in early versions of DB3?

BTW slightly off-topic, sry, but how buggy should we expect the initial releases of DB3 to be?

[Numsgil]

Will there be an optimizer in early versions of DB3?

I won't be writing it for early versions.  Someone else might, though.

BTW slightly off-topic, sry, but how buggy should we expect the initial releases of DB3 to be?

I'm aggressively unit tested things as I write them.  Of the things I've already written they should be fairly bug free.  The design for the physics engine is rather novel and not something I've completed, so there might be bugs there that cause some weird behavior (bots on the bottom of a stack getting pushed out of the world, things like that).

Not that DB2 is all that bug free anyway   The bar is set pretty low.

[jknilinux]

How long do you think it will take for DB3 to be nearly bug-free, after the first version is released?

[Numsgil]

No idea.  I don't have much experience with that part of the development lifecycle.  Bugs will have a higher priority than new features, though.