mikeash.com pyblog/performance-comparisons-of-common-operations.html comments

Compiled code? - 2012-03-10 15:34:28

Sat, 10 Mar 2012 15:34:28 GMT

Is it possible for you to also provide a compiled executable, simply for disassembly? (or attached the disassembled intel-syntax assembly code)

Just to allow us to see what's actually being executed, and if you provide an O3 and O0 version (I have no obj-c compiler atm) I'm sure we can fix it up so that O3 doesn't break any of the loops.

mikeash - 2008-01-13 05:02:49

Sun, 13 Jan 2008 05:02:49 GMT

Good idea. There were some interesting changes, read more here: http://www.mikeash.com/?page=pyblog/performance-comparisons-of-common-operations-leopard-edition.html

Ahruman - 2008-01-12 21:44:01

Sat, 12 Jan 2008 21:44:01 GMT

It’d be nice to see some Leopard numbers here. My tests on a 2.4 GHz iMac give about the same numbers for most things, but NSInvocation is twice as fast and objc message sends are slower. It’d be more interesting with numbers from the same computer.

mikeash - 2007-09-04 23:28:00

Tue, 04 Sep 2007 23:28:00 GMT

Marcel, obviously personal experiences will differ. I’ve written my share of high-performance software and never had memory allocation of any kind be an important factor. I would assume that individual programming styles will influence these things a lot, since if you subconsciously write code that does something less often, then you will not run into that particular trouble as frequently. 
 
In general I would say that if you’ve run into a problem a few times you should be experienced enough to know when to deal with it, and if you haven’t then you should follow the general principle of avoiding premature optimization, writing good, clean code, and waiting until you can profile to determine where the problems lie.

Marcel Weiher - 2007-09-01 18:58:00

Sat, 01 Sep 2007 18:58:00 GMT

My experience is that performance needs to be considered and designed for from the start. Not the “small efficiencies” whose pursuit has been characterized as the “root of all evil”, but the design choices that make good performance possible. Object-allocation patterns are definitely among the latter, not the former. This is not theory or corner cases, but hard won experience. YMMV.

leeg - 2007-08-29 09:28:00

Wed, 29 Aug 2007 09:28:00 GMT

OK, so now I stop talking from a position of ignorance and refer to my Paper Singh, specifically section 8.15 “Memory Allocation in User Space”. It seems that OS X does have scalable allocation categories, not quite the same as but analogous to Solaris large pages (because they’re not backed by large pages in the hardware – they just adapt the bookkeeping). Your 16b malloc()s are handled by a special case called the tiny region allocator, the quantum for which is exactly 16 bytes. Your 16M malloc()s are on the border of the large and huge allocations, I think they’re huge though. I’m slightly interested in finding out whether creating a 16M zone and doing the large malloc()s into that zone improves anything, but I currently have no use for that information as I have no reason to optimise malloc() calls anywhere. 
 
BTW you’re correct of course that pages are created/activated by faults, not by allocation. My mistake.

mikeash - 2007-08-29 01:04:00

Wed, 29 Aug 2007 01:04:00 GMT

I’m not sure what happens in the malloc itself exactly but I do know that the OS will put off a lot of the work until you actually start touching the pages. Since my test just does a malloc followed by an immediate free without ever writing to the pages, a great deal of that overhead is skipped.

leeg - 2007-08-28 18:48:00

Tue, 28 Aug 2007 18:48:00 GMT

Presumably large malloc()s are slow not only (and possibly not even mainly) due to “every allocation goes straight to the kernel and you pay for that in the form of syscall overhead” but also every allocation requires a large number of pages to be created, (zeroed? Not sure whether that happens because I never assume it does) and potentially other pages need to be added to the laundry list to let those new pages become activated. Solaris on SPARC has some ridiculously large page sizes (like 4M) in order to avoid a number of cache miss and paging operations happening so heavily in Oracle^Wapplications with large working data sets. 
 
Nice investigation.

mikeash - 2007-08-28 02:20:00

Tue, 28 Aug 2007 02:20:00 GMT

Marcel, anything can be the make-or-break factor in theory. Certainly in very specific types of code this can be the make-or-break factor in practice. But this falls solidly on the side of the line that says you shouldn’t even bother to think about it until after you have written an entire working program, determined it to be slow, and profiled it to find out why. Contrast with something like, say, spawning a new process in a loop which you know must execute at least 1000 times per second, where you should definitely be reconsidering your design from the start. 
 
Greg, thanks for the information on the dyld stub. That certainly explains why I saw no difference.

Greg Parker - 2007-08-28 01:11:00

Tue, 28 Aug 2007 01:11:00 GMT

Accelerated Objective-C dispatch on PPC is faster because it avoids the dyld stub (which is otherwise used for all cross-library calls). On i386 the dyld stub is much faster than the ppc equivalent, so we didn’t bother doing extra work to bypass it.

Marcel Weiher - 2007-08-28 01:03:00

Tue, 28 Aug 2007 01:03:00 GMT

Nice summary information! I would disagree somewhat on the conclusions, though: allocating objects often can be the make-or-break factor in terms of performance. See: <a href="http://www.metaobject.com/blog/2007/08/high-performance-objective-c-i.html" rel="nofollow">http://www.metaobject.com/blog/2007/08/h..<;/a>

Ahruman - 2007-08-27 16:06:00

Mon, 27 Aug 2007 16:06:00 GMT

Elliot, in your case compiler optimizations where probably converting the remainder operation to less costly operations. A quick checks shows that x % 82 compiles to mulhwu r5,r31,r30; srwi r5,r5,6; mulli r5,r5,82; subf r5,r5,r31 (multiply short unsigned, shift right; multiply short, subtract) on PPC, while x % y compiles to divwu r5,r31,r30; mullw r5,r5,r30; subf r5,r5,r31 (divide unsigned long, multiply long, subtract). The costly division is the explanation there. 
 
However, as you can see from the PPC assembler listing on my entry (linked above), the (unoptimized) benchmark code was generating division instructions for both the floating-point and the integer cases. I fully expect this was also the case in Mikes original x86 case.

Elliott Hughes - 2007-08-27 15:26:00

Mon, 27 Aug 2007 15:26:00 GMT

were the divisions by constants or non-constants? it makes a big difference, on both x86 and ppc. see here for details: <a href="http://elliotth.blogspot.com/2007/07/still-no-free-lunch-surprising-cost-of.html" rel="nofollow">http://elliotth.blogspot.com/2007/07/sti..<;/a>

Ahruman - 2007-08-27 13:34:00

Mon, 27 Aug 2007 13:34:00 GMT

Mike, accelerated dispatch is not implemented for x86. The private function rtp_init() (objc4/runtime/objc-rtp.m) does nothing if !defined(ppc). Looking into what rtp_init() actually does, the reason would seem to be that its easy to find a blr in (fixed-instruction-size) PPC code, but fiddly to do the equivalent for x86 code. Presumably the flag is quietly ignored on x86 so people dont have to fiddle about setting up GCC_FAST_OBJC_DISPATCH_ppc. 
 
Also, the export file has the non-nil entry points commented out, for both PPC and x86, with the helpful comment non-nil entry points disabled for now. I was really only interested in non-nil sends in the hope that they wouldnt actually be much more efficient. Still, if they were, there might conceivably be an advantage in putting performance-sensitive code which can make that assumption in a category in a separate file with custom build flags. Possibly. 
 
(Code extracts removed because Textile sucks.)

mikeash - 2007-08-26 21:08:00

Sun, 26 Aug 2007 21:08:00 GMT

Colin, thanks for the update. I hope you didn’t take my jab badly, it aroused legitimate curiosity and the results were a bit surprising, both in the allocation being slower and the drawing being faster than I expected. I had thought there would be about two orders of magnitude between them, not just one. 
 
Ahruman, thanks for the comparison. For the record, I compiled the code above with -O0 because -O3 screws up the do-nothing loops as you noted, and -O0 doesn’t seem to hurt anything for this particular test. I also tried accelerated Objective-C method dispatch and to my surprise, there was no effect on the results. I didn’t try non-nil receivers because I believe that it’s not a useful measurement for real code.

Ahruman - 2007-08-26 16:19:00

Sun, 26 Aug 2007 16:19:00 GMT

I intended to run the tests on a PPC last night, but forgot on account of brain not working at 2 am. (Its probably a good thing you distracted me from coding in that state.) Anyway, Ive posted them at <a href="http://jens.ayton.se/blag/performance-comparisons-of-common-operations-ppc-edition/" rel="nofollow">http://jens.ayton.se/blag/performance-co..<;/a> for space and formatting reasons. Spoiler: Objective-C message dispatch is not twice as fast as FP divide on PPC. 
 
Im not entirely satisfied about the accuracy of the smaller numbers, but the order is probably right.

Colin Barrett - 2007-08-26 02:39:00

Sun, 26 Aug 2007 02:39:00 GMT

I stand corrected, Mike. For what it’s worth, I discovered we were doing ObjC allocations in a similar situation anyway—looks like it was just my own preconceived notions and premature optimization at work.