On Mon, Nov 7, 2011 at 3:59 PM, Jens Alfke <j...@mooseyard.com> wrote: > On Nov 4, 2011, at 6:40 PM, Don Quixote de la Mancha wrote: > I store the grid as an array-of-arrays rather than a two dimensional > array. That is, I have an array of pointers which has the same number > of elements as there are rows. > > What’s the reason for that? I think it will hurt performance, both because > it’s more expensive to look up the rows, and because locality of reference > will suffer. Also, drawing will be slower because you can’t draw the entire > board in one blit as you could if it were a pixmap.
Naive implementations of Conway's Game of Life require two grids, one for the previous generation, with the other grid getting the new generation. To save memory, I only have two rows for the second grid. As the lines I am propagating advance downward, I place one of the two-line grid lines into the original grid, then replace it with the now out-of-date line from the original grid. This is just a preliminary implementation though. The rules of Conway's Life call for an infinite grid. The propagation speed of my presently finite grid scales with the area of the grid. It's real fast if I have one cell per screen pixel on an iOS device, but slows down very rapidly if I make it much bigger. For that reason I plan to move to a new algorithm that I have in mind that only stores the living cells, that is, the bits that are set to 1. The rules of Life strongly favor dead cells - 0 bits - so this will dramatically cut down on memory consumption. > (Actually, for best performance you should look into using a GPU shader > function to update the automaton. That should really scream, and I’d be > shocked if some enterprising demo-scene coder hasn’t implemented it > already.) This is for the iOS. Do iOS devices have hardware-acellerated video? My profiling with Instruments suggests that they don't because of the amount of time that the iOS spends doing block fills on behalf of my App. > At this point in my application there is only one thread. > > Yes, but the OS runs other threads for tasks like animations, network I/O, > etc. and those are allocating memory too. > > Also I'm pretty sure the iOS memory allocator is multithreaded, and > that Apple's code would be good about checking for runtime failures. > If it does not, then that is a bug in the iOS. > > The allocator is multithreaded; it’s your approach to backing out that’s not > thread-safe. If you accidentally eat up all available memory, you can’t > assume you have time to back out by freeing everything before anything else > tries/fails to allocate memory. There are other threads that could be > calling malloc at arbitrary times relative to your thread. > In general, higher-level code is not very graceful about handling > out-of-memory situations. That’s because they’re rare nowadays [although > less rare on iOS…] and because bulletproofing your code against them is > excruciatingly difficult. There are so very many memory allocations, and > once one fails you can’t do anything to handle the failure that might > allocate more memory (such as creating an error object…) I’ve dealt with > this in the Bad Old Days of the Classic OS, and it’s nearly impossible to > get right. Food for thought. Those would all still be iOS bugs, which Apple ought to know about. If my further investigation determines that something like that could be happening I will certainly file a bug. As it is I'm getting ready to write up a minimal test case to help determine whether it could be some completely unrelated bug elsewhere in my code. Before I started writing iOS code I did embedded systems development and Mac OS X device drivers. In both of those environments, Failure Is Not An Option. While you can certainly run out of memory or encounter other errors, one just has to back out gracefully. BTW a bug I already reported is that the Simulator allows simulated Apps a *LOT* more memory than do physical iOS devices. At least that was the case with some previous version of Xcode. I found that the Simulator would allow my App to have more or less the entire amount of address space available to any Mac OS X App. I advised Apple to use I think it was the setrlimit() system call to limit simulated Apps to the amount of memory a real iOS App would be expected to have. Their response? Submit a test case! Look man, how hard can it be? Just take any of Apple's sample iOS code, have it malloc() a gigabyte then run it in the Simulator. The allocation will succeed! It's quite likely that much of our tests in the Simulator that should fail really don't because OS X has far more reasources than is available to the iOS, and little or no effort is made to limit the resources available to simulated Apps. -- Don Quixote de la Mancha Dulcinea Technologies Corporation Software of Elegance and Beauty http://www.dulcineatech.com quix...@dulcineatech.com _______________________________________________ Cocoa-dev mailing list (Cocoa-dev@lists.apple.com) Please do not post admin requests or moderator comments to the list. Contact the moderators at cocoa-dev-admins(at)lists.apple.com Help/Unsubscribe/Update your Subscription: http://lists.apple.com/mailman/options/cocoa-dev/archive%40mail-archive.com This email sent to arch...@mail-archive.com