Q&A's, tips, howto's
Post Reply
Posts: 39
Joined: Mon Jan 11, 2010 9:41 pm


Post by Astrobe »

Arrays versus Lists

The deal is that lists are good at insertion and bad at random access, while arrays suck at insertion and are good at random access (I've measured a 30% difference on random accesses).
More often than not, one does a bit of both, so the choice between lists and arrays is not obvious; and it can evolve as the application evolves. However there is one case where the choice is simple: data structures, and objects. It seems to me that objects should be implemented as arrays rather than lists, because one typically perform random accesses to properties or fields of objects, and it seems unlikely that one needs to add/remove a field.


I've read that on current processors, one thing that matters as far as performance goes, are conditionnal jumps.
I have replaced the "if ladder" on lines 1547 and following with the switch() in function evaluateExpression(), and moved the second if statement (cell->type is symbol or context) in the switch statement below. I observed a gain of performance between 7% and 10%.

However this kind of micro-optimisation is very volatile and depends a lot on the compiler, the processor, and the context. If I replace the "if ladder" near line 1525 by a switch case on args-type, I observe a slight loss in performance. My "benchmark" is a broken implementation of the map operator with a for loop. I'm not sure if it's actually "good" way to measure performance. I think we need a set of standard benchmarks.

Posts: 5288
Joined: Thu Sep 26, 2002 4:45 pm
Location: Pasadena, California

Re: Optimisations

Post by Lutz »

There is a benchmark suite in newlisp-x.x.x/qa-specific-tests/qa-bench which can be used as follows from the newlisp-x.x.x directory:

Code: Select all

./newlisp qa-specific-tests/qa-bench
… runs each non-I/O primitive a number of times and reports a benchmark score compared to a calibration on a specific CPU - currently MacOSX 10.9 on a 2.3GHz Intel Core i5 Mac Mini.

Code: Select all

./newlisp qa-specific-tests/qa-bench calibrate
… does a calibration by measuring for each primitive the number of times to run the test routine until 1000 ms have passed. This mode generates a file primes.lsp, which is a list of all primitives tested with the calibration number. The list is then integrated into the qa-bench file replacing the existing list (around line number 80).

Calibration insures, that at least on the calibration platform each primitive is tested for the same time and goes with the same weight into the overall score.

Code: Select all

./newlisp qa-specific-tests/qa-bench report
… this mode reports a test time for each primitive and is around 10 ms for each function when testing on the calibration platform. This is useful to check performance impact of code changes on specific functions.

The report mode is not enabled on qa-bench in versions 10.5.7 and 10.5.8 but works fine on versions up to 10.5.6 calibrated for a Mac OSX, 1.83 GHz Core 2 Duo Mac Mini. The report mode also works on the 10.6.0-in progress release for MacOSX 10.9 on a 2.3GHz Intel Core i5 Mac Mini.

http://www.newlisp.org/downloads/develo ... nprogress/

Running qa-bench on different platforms gives dramatic differences when looking at the individual function profiles with the report option. There are huge differences for operating systems and compilers even running on the same hardware. Sometimes just the OS or compiler version makes a big difference.

Posts: 604
Joined: Fri Apr 08, 2005 7:13 pm
Location: Front Royal, Virginia

Re: Optimisations

Post by rickyboy »

VERY interesting! Many thanks!
(λx. x x) (λx. x x)

Post Reply