Obj-C circular buffer object, implementing one?

Question

Hi! I've been developing for the iPhone for quite some time and I've been wondering if there's any array object that uses circular buffer in Obj-C? Like Java's Stack or List or Queue. I've been tinkering with the NSMutableArray, testing it's limits... and it seems that after 50k simple objects inside the array - the application is significantly slowed down.

So, is there any better solution other than the NSMutableArray (which becomes very slow with huge amounts of data). If not, can anyone tell me about a way to create such an object (would that involve using chain (node) objects??).

Bottom line: Populating a UITableView from an SQLite DB directly would be smart? As it won't require memory from an array or anything, but just the queries. And SQLite is fast and not memory grinding.

Thank you very much for you time and attention, ~ Natanavra.

Answer 1

Objective-C objects are not really "simple," so 50,000 of them is going to be pretty demanding. Write your own in straight C or C++ if you want to avoid the bottlenecks and resource demands of the Objective-C runtime.

A rather lengthy and non-theoretical discussion of the overhead associated with convenience:

http://www.cocoabuilder.com/archive/cocoa/35145-nsarray-overhead-question.html#35128

And some simple math for simple people:

All it takes to make an object as opposed to a struct is a single pointer at the beginning.

Let's say that's true, and let's say we're running on a 32-bit system with 4 byte pointers.

4 bytes x 50,000 objects = 200000 bytes

That's nearly 200MB worth of extra memory that your data suddenly needs just because you used Objective-C. Now compound that with the fact that whatever NSArray you add those objects to is going to double that by keeping its own set of pointers to those objects and you've just chewed up 400MB of RAM just so you could use a couple of convenience wrappers.

Refresh my memory here... Are swap files on hard drives as fast as RAM? How much RAM is there in an iPhone? How many function calls and stack frames does it take to send an object a message? Why isn't IOKit written in Objective-C? How many of Apple's flagship applications that do a lot of DSP use AppKit? Anybody got a copy of otool they can check with? I'm seeing zero here.

Answer 2

It's trivial to have NSMutable array act like a stack, list, queue etc using the various insertObject:atIndex: and removeObjectAtIndex: methods. You can write your own subclasses if you want to hardwire the behavior.

I doubt the performance problems you are seeing are being caused by NSMutableArray especially if your point of reference is the much, much slower Java. The problem is most likely the iPhone itself. As noted previously, 50,000 objective-c objects is not a trivial amount of data in this context and the iPhone hardware may struggle to managed that much data.

If you need some kind of high performance array for bytes, you could use one of the core foundation arrays or roll your own in plain C and then wrap them in a custom class.

It sounds to me like you need to switch to core data so you don't have to keep all this in memory. Core data will efficiently fetch what you want only when you need it.

Answer 3

Apologies for tooting my own horn, but I implemented a C-based circular buffer in CHDataStructures. (Specifically, check out CHCircularBufferQueue and CHCircularBufferStack.) The project is open source and has benchmarks which demonstrate that a true circular buffer is quite fast when compared to NSMutableArray in the general case, but results will depend on your data and usage, as well as the fact that you're operating on a memory-constrained device (e.g. iPhone). Hope that helps!

Answer 4

If you're seeing performance issues, measure where your app is spending its time, don't just guess. Apple provides an excellent set of performance measurement tools.

Answer 5

You can use STL classes in "Objective-C++" - which is a fancy name for Objective-C making use of C++ classes. Just name those source files that use C++ code with a ".mm" extension and you'll get the mixed runtime.

Answer 6

From what I've been thinking it seems that going for Quinn's class is the best option possibly. I have another question - would it be faster or smarter to load everything straight from the SQLite DB instead of creating an object and pushing it into an array?

Thank you in advance, ~ Natanavra.