very different execution time

  • I have two versions of a class for the production of permutations.
    In one the permutation is numbers in an int array, in the other
    objects in a NSMutableArray.
    There is a huge difference in execution time between these two
    versions. When the array version takes 135 seconds, the corresponding
    calculation with NSMutableArray takes 700 seconds; using
    exchangeObjectAtIndex:withObjectAtIndex: takes even 25% more. Without
    the specific array operations the time needed is not much less then
    for the array version. I therefore conclude that the replace
    operations in NSMutableArray are responsible for the huge difference.
    However, given that in the one integers are assigned and in the other
    pointers, I have difficulties to understand the magnitude of the
    difference. Could it be the object message sending mechanism? Perhaps
    I have something wrong? If that difference is real and without cure,
    what causes it?
    I hope someone will provide the answer.

    The operations concerned are in a recursive method of which the core is:

    if (steps[level] > 0) { i = --steps[level];
      unsigned int tmp = permutation[i];
      permutation[i] = permutation[i + 1]; permutation[i + 1] = tmp;
    } else if (level > 0) {
      unsigned int tmp = permutation[0];
      for (i = 0; i < level; i++) { permutation[i] = permutation[i + 1]; }
      permutation[level] = tmp;
      [self nextlevel: level]; ...
    }

    and for the Foundation collection:
    if (steps[level] > 0) { i = --steps[level];
      id temp = [theValues objectAtIndex: i];
      [theValues replaceObjectAtIndex: i withObject: [theValues
    objectAtIndex: (i + 1)]];
      [theValues replaceObjectAtIndex: (i + 1) withObject: temp];
    } else if (level > 0) {
      id temp = [theValues objectAtIndex: 0];
      for (i = 0; i < level; i++) {
        [theValues replaceObjectAtIndex: i withObject: [theValues
    objectAtIndex: (i + 1)]];
      }
      [theValues replaceObjectAtIndex: level withObject: temp];
      [self nextlevel: level]; ...
    }

    Hans van der Meer
  • I wrote an application that extensively uses array to store things in
    actually sort of matrices, somewhat hollow, beside NSCollection
    subclasses that can't contain nil and i had therefore to pass NSNull
    and test everything,
    it came out that nsarray (and to some extent cfarray) are very slow.
    So i wrote an entire calse of mutable arrays I called ObjectCArray
    because it behaves exactly the same, you can store objects wherever
    you want,

    The test application, with 10Millions objects gives the results
    below: Note that the test is done fairly, the code is exactly the
    same for both.
    The only thing that is faster with NSMutableArrays is the allocation.

    ObjectCArray[8514] Testing allocation...
    ObjectCArray[8514] -> 0.068420s
    ObjectCArray[8514] Testing insertion...
    ObjectCArray[8514] -> 4.910978s
    ObjectCArray[8514] Testing overwrite...
    ObjectCArray[8514] -> 8.302022s
    ObjectCArray[8514] Testing removal...
    ObjectCArray[8514] -> 5.118968s
    ObjectCArray[8514] Testing isEqual: search...
    ObjectCArray[8514]     Searching a non existing object.
    ObjectCArray[8514] Non existing string not found: OK
    ObjectCArray[8514] -> 0.018265s
    ObjectCArray[8514]     Searching an existing object. (@"Hello World")
    ObjectCArray[8514] Existing string found: OK
    ObjectCArray[8514] -> 0.017532s
    ObjectCArray[8514] Testing release
    ObjectCArray[8514] -> 0.014179s
    ObjectCArray[8514] Comparing with NSMutableArray
    ObjectCArray[8514] NSMutableArray allocation...
    ObjectCArray[8514] -> 0.000114s
    ObjectCArray[8514] NSMutableArray insertion...
    ObjectCArray[8514] -> 8.853487s
    ObjectCArray[8514] NSMutableArray overwrite...
    ObjectCArray[8514] -> 8.846627s
    ObjectCArray[8514] NSMutableArray removal...
    ObjectCArray[8514] -> 5.709873s
    ObjectCArray[8514] NSMutableArray isEqual: search...
    ObjectCArray[8514]     Searching a non existing object.
    ObjectCArray[8514] Non existing string not found: OK
    ObjectCArray[8514] -> 0.307552s
    ObjectCArray[8514]     Searching an existing object. (@"Hello World")
    ObjectCArray[8514] Existing string found: OK
    ObjectCArray[8514] -> 0.307589s
    ObjectCArray[8514] NSMutableArray release
    ObjectCArray[8514] -> 0.539352s

    On Sep 28, 2007, at 1:52 PM, Hans van der Meer wrote:

    > I have two versions of a class for the production of permutations.
    > In one the permutation is numbers in an int array, in the other
    > objects in a NSMutableArray.
    > There is a huge difference in execution time between these two
    > versions. When the array version takes 135 seconds, the
    > corresponding calculation with NSMutableArray takes 700 seconds;
    > using exchangeObjectAtIndex:withObjectAtIndex: takes even 25% more.
    > Without the specific array operations the time needed is not much
    > less then for the array version. I therefore conclude that the
    > replace operations in NSMutableArray are responsible for the huge
    > difference. However, given that in the one integers are assigned
    > and in the other pointers, I have difficulties to understand the
    > magnitude of the difference. Could it be the object message sending
    > mechanism? Perhaps I have something wrong? If that difference is
    > real and without cure, what causes it?
    > I hope someone will provide the answer.
    >
    > The operations concerned are in a recursive method of which the
    > core is:
    >
    > if (steps[level] > 0) { i = --steps[level];
    > unsigned int tmp = permutation[i];
    > permutation[i] = permutation[i + 1]; permutation[i + 1] = tmp;
    > } else if (level > 0) {
    > unsigned int tmp = permutation[0];
    > for (i = 0; i < level; i++) { permutation[i] = permutation[i + 1]; }
    > permutation[level] = tmp;
    > [self nextlevel: level]; ...
    > }
    >
    > and for the Foundation collection:
    > if (steps[level] > 0) { i = --steps[level];
    > id temp = [theValues objectAtIndex: i];
    > [theValues replaceObjectAtIndex: i withObject: [theValues
    > objectAtIndex: (i + 1)]];
    > [theValues replaceObjectAtIndex: (i + 1) withObject: temp];
    > } else if (level > 0) {
    > id temp = [theValues objectAtIndex: 0];
    > for (i = 0; i < level; i++) {
    > [theValues replaceObjectAtIndex: i withObject: [theValues
    > objectAtIndex: (i + 1)]];
    > }
    > [theValues replaceObjectAtIndex: level withObject: temp];
    > [self nextlevel: level]; ...
    > }
    >
    > Hans van der Meer
  • Yes, NSMutableArray primitive operations are much slower than a straight C
    array would be. Usually this doesn't matter, because usually the time spent
    manipulating arrays is only a small fraction of total time.

    If you want high performance, with a richer interface (such as easy ability
    to resize) than plain C arrays, consider using Objective-C++ and STL.

    --
    Scott Ribe
    <scott_ribe...>
    http://www.killerbytes.com/
    (303) 722-0567 voice
  • Performance of Cocoa collection classes and their YellowBox/Openstep/NeXTstep predecessors have been discussed for 19 years now.  Surely a little google search can inform this 10,000th iteration of this thread ;)

      The best analysis is the optimization series at , and for this conversation, look at <A href="http://www.mulle-kybernetik.com/artikel/Optimization/opti-4.html">http://www.mulle-kybernetik.com/artikel/Optimization/opti-4.html.
previous month september 2007 next month
MTWTFSS
          1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30
Go to today