Cpp version

[jknilinux]

Hello everyone...  

OK, I'm planning on making a DB fork. It's a little ambitious, but then again, so is the whole DB project.
My #1 concern is speed and simulation size. I'm thinking you're more likely to evolve complex behavior if you run a large sim for a long time, maybe 100 megacycles or more, as opposed to making a more complex sim but running it for only a megacycle. I don't think 10 cps for a large sim is an ideal goal. So, I'm thinking of continuing DB 2.5. Here's the plan:

1: Finish the DB 2.5 Cpp port, then add features such as shadows, improved multibot/sexrepro design, self-modifying code, maybe size changing, etc...
(3D graphics and other potentially time-consuming, difficult-to-implement features aren't necessary)

2: Find out how to take advantage of multiple cores/multiple computers, such as utilizing a beowulf cluster, maybe even use GPGPUs one day (there are versions of Cpp for GPGPU programming)

3: Finally, get the finished DB program to run in an extremely fast OS, such as MenuetOS or DSL.

My goal is 500-1,000 cps for a large sim. Using a Beowulf cluster running DB2.5 in a very lightweight OS, this should be possible, right?
My ultimate goal, though, is to make a cluster running a stripped-down OS which itself only runs DB, making it a DB-centric "supercomputer".



Here are my concerns...
1: What problems does DB 2.5 still have? How hard will it be to finish it?
2: How difficult would it be to implement these new features?
3: How difficult would it be to make it multicore/multithread/multicomputer compatible?
4: How much of a speedup can I expect?
5: Do you think it's worth it? Can I expect more interesting evolution in this program than in DB3?


Right now, I'm under the impression this won't be too difficult. DB2 already can spread organisms from sim to sim. DB2.5 is half-done. Thus, a preliminary version of DB2.44 in CPP with organism sharing will be easy to implement, right?

Thanks for your help!!!

[Numsgil]

3: Finally, get the finished DB program to run in an extremely fast OS, such as MenuetOS or DSL.

My goal is 500-1,000 cps for a large sim. Using a Beowulf cluster running DB2.5 in a very lightweight OS, this should be possible, right?

No.

A lightweight os is not faster than a heavy one. Programs are run in hardware after all (assembly is not an interpreted language!). Differences are in the amount of ram overhead the os takes up.

Second, 1000 cycles a second with 1000 bots in 2.5 or 2 is impossible with extant hardware, super computers included.  Those versions are architected like video games. They have highly serial architectures. See Amdahls law.  See extant physics engines (havok or box 2d).  They can't run 1000s of bodies at 1000s of fps.

Db3 by comparison is architected to be less serial. So one cycle might take a full minute but others are entirely free.  Throughput over latency.

Here are my concerns...
1: What problems does DB 2.5 still have? How hard will it be to finish it?

It's feature complete but buggy...  So it's like that old programming addage: the last 10% takes 90% of the time.

2: How difficult would it be to implement these new features?

Not harder than doing it with the current VB version.  The two are quite similar.

3: How difficult would it be to make it multicore/multithread/multicomputer compatible?

Scaling to a few processors wouldn't be too hard a long as you were smart with how you did it. More than that is a case of diminishing returns. See amdals law.

4: How much of a speedup can I expect?

10% over the current code unless you break it in to multithreading for more hardware threads. Then you might be able to scale sub linearly with number of hardware threads.

5: Do you think it's worth it? Can I expect more interesting evolution in this program than in DB3?

Not for the effort.  Probably not more interesting than db3 would theoretically produce, either.  It's a case of a simple environment producing simple results.  So the bots would evolve to a plateau.

...

I'd greatly prefer and recommend work being done in either the current version or db3. But if you're really gung ho about the whole thing then go for it.  Some lessons are hard to swallow until you experience them. I'll try to set you up with write access to the cpp repository when I get back on Friday.

[jknilinux]

so, we can actually expect a performance increase in DB3 on multi-core computers over DB2?

[Numsgil]

Yeah, eventually. I still have to code thread pools in, but much of the code is friendly to multithreading.

[jknilinux]

what about single-core computers?

[Numsgil]

There are some high level algorithmic optimizations that might be made that would speed up things considerably. But those are later on down the road.  Initial versions will be much slower.

[jknilinux]

How slow are we talkin for initial versions? DB2 speed? half that? Why will they be so slow?

Also, how much experience do you have with bigO optimization? Will implementing such algorithms be difficult/unavailable in initial releases? At what point do you think DB3 will reach a usable level?

Also, can we implement some sort of 2.5D mode, so it won't actually have to deal with 3D graphics? Maybe a memory location that, if set to 1, brings the bot to a parallel 2D sim, moving it slightly in the 3rd dimension, where things in each 2D level can only interact with that which is in their level. It can switch back to 0 if it wants to return to the original one. Maybe we can implement each 2D sim in this mode on a different core/computer? on second thought, this would be a great way to induce speciation by setting slightly different physics to each parallel 2D plane... Perhaps we can use this as an alternative to the roving teleporter option too for IM?

Same with 3D, you can make it 3.5D where bots can move slightly into the fourth dimension by setting some value to 1 in memory. IMO, better idea than roving teleporter. This way, bots can choose to leave the sim or not.

[Numsgil]

How slow are we talkin for initial versions? DB2 speed? half that? Why will they be so slow?

For physics, I'm not using a broadphase yet, so collisions will be O(n^2) instead of O(n). Worse, collision response is using dense matrix factorization, so "islands" of bots will be O(n^3) instead of O(n) like sparse matrix math would give.  On the plus side information will be cached between frames so in a zero bot sim where nothing is moving it will probably be much faster.  

Also, how much experience do you have with bigO optimization? Will implementing such algorithms be difficult/unavailable in initial releases? At what point do you think DB3 will reach a usable level?

I do program real time systems for a living so I'm not exacly out of my element here. Initial releases won't have them because it would take extra time and I just really want somthing for users to play with sooner rather than later. I'll prioritize speed vs features based on initial feedback. The algorithms are difficult to program (testing needs to be rigorous especially) because they rely on high level math that not everyone is familiar with. If someone wants to tackle one of the problems I think it would make a good project.  They're conceptually self contained, and I can partly walk people through the math involved.

Also, can we implement some sort of 2.5D mode, so it won't actually have to deal with 3D graphics?

DB3 won't be 3D. I was considering it at first but I changed my mind because it would have been difficult to build a good control scheme for bots and even users.  The graphics use a custom built 2d wrapper around 3d xna, though, so they are 3d in a manner of speaking (hardware accelerated cards treat 2d as 3d basically).

Maybe a memory location that, if set to 1, brings the bot to a parallel 2D sim, moving it slightly in the 3rd dimension, where things in each 2D level can only interact with that which is in their level. It can switch back to 0 if it wants to return to the original one. Maybe we can implement each 2D sim in this mode on a different core/computer? on second thought, this would be a great way to induce speciation by setting slightly different physics to each parallel 2D plane... Perhaps we can use this as an alternative to the roving teleporter option too for IM?

Interesting idea. When I get to working on teleporters I'll see what can be done.