Thursday, March 27, 2014

Exposing NSMutableArray

Bartosz Ciechanowski:

Inserting object at index 0 uses the circular buffer magic to put the newly inserted object at the end of the buffer.


Whenever the buffer gets full, it is reallocated with 1.625 times larger size. […] Mike Curtiss has provided a very good explanation of why making resizing factor equal to 2 is suboptimal.


This is a shocker – __NSArrayM never reduces its size!


I’ve always had this idea of Foundation being a thin wrapper on CoreFoundation. My argument was simple – there is no need to reinvent the wheel with brand new implementations of NS* classes when the CF* counterparts are available. I was shocked to realize neither NSArray nor NSMutableArray have anything in common with CFArray.


Basically, CFArray moves the memory around to accommodate the changes in the most efficient fashion, similarly to how __NSArrayM does its job. However, the CFArray does not use a circular buffer! Instead it has a larger buffer padded with zeros from both ends which makes enumeration and fetching the correct object much easier. Adding elements at either end simply eats up the remaining padding.

Update (2014-04-14): David Smith notes that the Core Foundation creation functions will often now give you NS objects, whereas it used to be the reverse. Removing the Core Foundation layer yielded a 10–40% speed improvement. Marcel Weiher notes that the NS collections were originally faster and Core Foundation was a regression, for political reasons.

1 Comment RSS · Twitter

[...] See also Exposing NSMutableArray. [...]

Leave a Comment