multidimensional arrays
-
Hi All,
I've run into a situation where it would be great to have a
multidimensional NSArray or NSMutableArray. Is there such a class? If
not, any suggestions on the most elegant solution?
Thanks,
Daniel -
On Mar 14, 2005, at 12:19 PM, Daniel Child wrote:> Hi All,Why not just implement them as they are in 99.9% of other
>
> I've run into a situation where it would be great to have a
> multidimensional NSArray or NSMutableArray. Is there such a class? If
> not, any suggestions on the most elegant solution?
langauges/frameworks - an array of arrays.
Bob -
On 14 Mar 2005, at 12:28, Thomas Davie wrote:>> I've run into a situation where it would be great to have a
>> multidimensional NSArray or NSMutableArray. Is there such a class? If
>> not, any suggestions on the most elegant solution?
> Why not just implement them as they are in 99.9% of other
> langauges/frameworks - an array of arrays.
Actually quite a few languages implement them as a single array of size
rows * cols and do the necessary arithmetic on the index to hit the
right slot. That's an approach that would work with NSArrays too.
In general (and in psuedocode)
int x[cols, rows] ==> int x[cols * rows]
x[c, r] = n ==> x[c * rows + r] = n
I'd assume, without having given it too much thought, that a category
could be added to NS(Mutable)Array to do the same.
--
Andy Armstrong, hexten.net -
On 2005-03-14, at 13.34, Andy Armstrong wrote:> Actually quite a few languages implement them as a single array of
> size rows * cols and do the necessary arithmetic on the index to hit
> the right slot. That's an approach that would work with NSArrays too.
>
> In general (and in psuedocode)
>
> int x[cols, rows] ==> int x[cols * rows]
>
> x[c, r] = n ==> x[c * rows + r] = n
>
> I'd assume, without having given it too much thought, that a category
> could be added to NS(Mutable)Array to do the same.
Wouldn't that require that NSArray supported that some indexes are not
populated with data (which it doesn't)?
Of course, you could pre-populate your array with dummy data ([NSNull
null] or similar), in which case it would probably work like you
suggest.
j o a r -
On Mar 14, 2005, at 12:39 PM, j o a r wrote:>Not if you impose a similar constraint that Multi-dimensional arrays
> On 2005-03-14, at 13.34, Andy Armstrong wrote:
>
>> Actually quite a few languages implement them as a single array of
>> size rows * cols and do the necessary arithmetic on the index to hit
>> the right slot. That's an approach that would work with NSArrays too.
>>
>> In general (and in psuedocode)
>>
>> int x[cols, rows] ==> int x[cols * rows]
>>
>> x[c, r] = n ==> x[c * rows + r] = n
>>
>> I'd assume, without having given it too much thought, that a
>> category could be added to NS(Mutable)Array to do the same.
>
> Wouldn't that require that NSArray supported that some indexes are
> not populated with data (which it doesn't)?
>
> Of course, you could pre-populate your array with dummy data ([NSNull
> null] or similar), in which case it would probably work like you
> suggest.
must have data in all of their slots (just like the current
uni-dimensional arrays). I've always found it a bit strange that cocoa
imposes this condition on arrays, they are after all meant to be
arrays, not lists.
Bob -
On 14 Mar 2005, at 12:39, j o a r wrote:> Wouldn't that require that NSArray supported that some indexes are not
> populated with data (which it doesn't)?
Does it? Why? It's no different from the single index case apart from
the fact that the indexes are computed.> Of course, you could pre-populate your array with dummy data ([NSNull
> null] or similar), in which case it would probably work like you
> suggest.
Or even not do that in which case it'll still work like I suggest :)
--
Andy Armstrong, hexten.net -
*remembers to send it to the list*
Begin forwarded message:> From: Thomas Davie <tom.davie...>
> Date: March 14, 2005 12:55:43 PM BST
> To: j o a r <joar...>
> Cc: Andy Armstrong <andy...>, Cocoa-Dev Development
> <cocoa-dev...>
> Subject: Re: multidimensional arrays
>
>
> On Mar 14, 2005, at 12:39 PM, j o a r wrote:
>
>>
>> On 2005-03-14, at 13.34, Andy Armstrong wrote:
>>
>>> Actually quite a few languages implement them as a single array of
>>> size rows * cols and do the necessary arithmetic on the index to
>>> hit the right slot. That's an approach that would work with
>>> NSArrays too.
>>>
>>> In general (and in psuedocode)
>>>
>>> int x[cols, rows] ==> int x[cols * rows]
>>>
>>> x[c, r] = n ==> x[c * rows + r] = n
>>>
>>> I'd assume, without having given it too much thought, that a
>>> category could be added to NS(Mutable)Array to do the same.
>>
>> Wouldn't that require that NSArray supported that some indexes are
>> not populated with data (which it doesn't)?
>>
>> Of course, you could pre-populate your array with dummy data
>> ([NSNull null] or similar), in which case it would probably work
>> like you suggest.
> Not if you impose a similar constraint that Multi-dimensional arrays
> must have data in all of their slots (just like the current
> uni-dimensional arrays). I've always found it a bit strange that
> cocoa imposes this condition on arrays, they are after all meant to
> be arrays, not lists.
>
> Bob -
Would a simple array of structures serve your needs? I've used
that a few times.
--Jim -
> Hi All,
>
> I've run into a situation where it would be great to have a
> multidimensional NSArray or NSMutableArray. Is there such a class? If
> not, any suggestions on the most elegant solution?
>
> Thanks,
> Daniel
It's actually one of the major annoyances (to me anyway) of working in
pure Obj-C code on this project: there is no direct support for
multi-dimensional arrays, or even static arrays of PODs. Implementing
an NSArray of NSArrays just feels ugly, and the syntax to access items
is awful. And having to revert to good old-fashioned C-style indexing
(e.g. myArray[y * rowLength + x]) is annoying. Since my arrays are part
of larger objects, I end up writing an accessor that looks like [self
itemAt:x:y]. I miss the simpler myArray[x][y] syntax of C++, and the
STL containers, and the temptation is always there to start mixing the
two languages; but I swore to myself I'd write this app in pure Obj-C
so I could honestly know what it's like. -
On Mar 14, 2005, at 7:03 PM, Serge Meynard wrote:>> Hi All,All I can say is:
>>
>> I've run into a situation where it would be great to have a
>> multidimensional NSArray or NSMutableArray. Is there such a class?
>> If not, any suggestions on the most elegant solution?
>>
>> Thanks,
>> Daniel
>
> It's actually one of the major annoyances (to me anyway) of working
> in pure Obj-C code on this project: there is no direct support for
> multi-dimensional arrays, or even static arrays of PODs. Implementing
> an NSArray of NSArrays just feels ugly, and the syntax to access
> items is awful. And having to revert to good old-fashioned C-style
> indexing (e.g. myArray[y * rowLength + x]) is annoying. Since my
> arrays are part of larger objects, I end up writing an accessor that
> looks like [self itemAt:x:y]. I miss the simpler myArray[x][y] syntax
> of C++, and the STL containers, and the temptation is always there to
> start mixing the two languages; but I swore to myself I'd write this
> app in pure Obj-C so I could honestly know what it's like.
#define x<y> [x objectAtIndex:y]
Bob -
On Mar 14, 2005, at 11:03 AM, Serge Meynard wrote:>> Hi All,
>>
>> I've run into a situation where it would be great to have a
>> multidimensional NSArray or NSMutableArray. Is there such a class? If
>> not, any suggestions on the most elegant solution?
>>
>> Thanks,
>> Daniel
>
> It's actually one of the major annoyances (to me anyway) of working in
> pure Obj-C code on this project: there is no direct support for
> multi-dimensional arrays, or even static arrays of PODs. Implementing
> an NSArray of NSArrays just feels ugly, and the syntax to access items
> is awful. And having to revert to good old-fashioned C-style indexing
> (e.g. myArray[y * rowLength + x]) is annoying. Since my arrays are
> part of larger objects, I end up writing an accessor that looks like
> [self itemAt:x:y]. I miss the simpler myArray[x][y] syntax of C++, and
> the STL containers, and the temptation is always there to start mixing
> the two languages; but I swore to myself I'd write this app in pure
> Obj-C so I could honestly know what it's like.
You do realize that C fully supports multi-dimensional arrays, you can
do myArray[x][y] in plain C (and Objective-C is super set of C). In a
couple of lines of code one could use NSData to manage the memory for
the array (if you want to avoid malloc and/or use Cocoa memory
management scheme), etc. and wrap it up in a multidimensional array
class and go wild. With a little more work you could support sparse
multidimensional arrays if memory is a concern.
If you think Cocoa is missing something file an enhancement request
(countless examples of new methods/classes in Cocoa that come from such
requests)...
<http://developer.apple.com/bugreporter/>
I also bet several freely available third party Objective-C classes
exist that do what you want.
-Shawn -
> You do realize that C fully supports multi-dimensional arrays, you can
> do myArray[x][y] in plain C (and Objective-C is super set of C).
Only if your array size is fixed at compile-time. I'm talking about
arrays whose size is only known at execution time, and are allocated
dynamically. -
On 14 Mar 2005, at 19:56, Serge Meynard wrote:>> You do realize that C fully supports multi-dimensional arrays, you
>> can do myArray[x][y] in plain C (and Objective-C is super set of C).
>
> Only if your array size is fixed at compile-time. I'm talking about
> arrays whose size is only known at execution time, and are allocated
> dynamically.
#include <stdlib.h>
int main(void) {
int **x, i;
x = malloc(10 * sizeof(int *));
for (i = 0; i < 10; i++) {
x[i] = malloc(10 * sizeof(int));
}
x[0][0] = 1;
return 0;
}
Looks pretty dynamic to me :)
--
Andy Armstrong, hexten.net -
On 14 Mar, 2005, at 1:56 PM, Serge Meynard wrote:>> You do realize that C fully supports multi-dimensional arrays, you
>> can do myArray[x][y] in plain C (and Objective-C is super set of C).
>
> Only if your array size is fixed at compile-time. I'm talking about
> arrays whose size is only known at execution time, and are allocated
> dynamically.
Read more than the first sentence. The next sentence was "In a couple
of lines of code one could use NSData to manage the memory for the
array..." i.e. dynamic allocation.
Glen -
Serge Meynard wrote:>> You do realize that C fully supports multi-dimensional arrays, you can
>> do myArray[x][y] in plain C (and Objective-C is super set of C).
>
>
> Only if your array size is fixed at compile-time. I'm talking about
> arrays whose size is only known at execution time, and are allocated
> dynamically.
In C, only the first dimension can be of unbounded size. The type and size
of the elements of a C array must be known at compile time, and that
includes lesser dimensions of an array of arrays.
If you are talking about a MyArray class in C++, that allows myArray[x][y]
access to arbitrary data, you are not talking C arrays. Rather, you are
talking syntactic sugar via operator overloading to an array that contains
array pointers. The underlying operation is still myArray->get (x,y).
You can do the equivalent in Objective-C:
@interface My2DArray : NSObject
{
NSArray * mArray;
}
- (id) objectAtIndex: (unsigned int) x index: (unsigned int) y;
@end
@implementation My2DArray : NSObject
- (id) objectAtIndex: (unsigned int) x index: (unsigned int) y
{
return
[((NSArray *) [objectAtIndex: x]) objectAtIndex: y];
}
@end
Add other messages to suit.
Note that NSArray is not semantically equivalent to a C array.
C array:
- statically typed to any single _statically sized_ type
NSArray
- dynamically sized
- Holds non-nil NSObject, including subclasses
- Implements retain / release semantics on entries
Implementing a class that allows more C-array like semantics isn't hard,
but you either need to use NSDictionary or do your own memory management.
--
Andrew White
--------------------------------------------------------------------------
This email and any attachments are confidential. They may contain legally
privileged information or copyright material. You should not read, copy,
use or disclose them without authorisation. If you are not an intended
recipient, please contact us at once by return email and then delete both
messages. We do not accept liability in connection with computer virus,
data corruption, delay, interruption, unauthorised access or unauthorised
amendment. This notice should not be removed. -
2005-03-14 kl. 20.56 skrev Serge Meynard:>> You do realize that C fully supports multi-dimensional arrays, you
>> can do myArray[x][y] in plain C (and Objective-C is super set of C).
>
> Only if your array size is fixed at compile-time. I'm talking about
> arrays whose size is only known at execution time, and are allocated
> dynamically.
If you want it on the stack, C99 supports variable sized arrays. If
not, just malloc.
But for heap allocated memory, there's no way to get [][] syntax
without ** references and you'll want avoid that as it will cost two
memory access to access a single array element ( not counting operator
overloading, which might not compile down do a direct memory access ).
Especially if you'll be using this in loops, where the compiler may not
be able to move a constant row indexing out of the loop ( if you array
wasn't declared doubly restricted, e.g. ).
Since your access is going to be array+x*ysize+y or array+y*xsize+x
anyway, does it really matter what syntax you use?
The reason there is no multi dimensional NSArray class is probably that
you seldom need multi dimensional arrays of Cocoa objects. Typically
you need multi dimensional arrays in the lower levels of your program,
and there wrapping a multidimensional array in ObjC imposes a lot of
unnecessary overhead and makes it hard to pass your data to C and C++
functions without breaking encapsulation.
. . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . .
. <waterspirit...> . . www.synapticpulse.net . -
> But for heap allocated memory, there's no way to get [][] syntax
> without ** references and you'll want avoid that as it will cost two
> memory access to access a single array element ( not counting
> operator overloading, which might not compile down do a direct memory
> access ). Especially if you'll be using this in loops, where the
> compiler may not be able to move a constant row indexing out of the
> loop ( if you array wasn't declared doubly restricted, e.g. ).
>
> Since your access is going to be array+x*ysize+y or array+y*xsize+x
> anyway, does it really matter what syntax you use?
Then you just have to ask whether your array is small enough to fit in
cache (or used in small enough parts to fit in cache), because two
cache hits is gonna be a lot faster than one cache hit, and a multiply.
This is the level at which optimization gains you nothing but
obfuscated code - you probably gain 0.001 seconds on one chip and loose
the same on a different chip... So stop trying to find that one clock
cycle difference it makes and start trying to (a) write code that looks
nice, and (b) write fast algorithms.
Bob -
2005-03-15 kl. 13.02 skrev Thomas Davie:>> But for heap allocated memory, there's no way to get [][] syntax
>> without ** references and you'll want avoid that as it will cost two
>> memory access to access a single array element ( not counting
>> operator overloading, which might not compile down do a direct memory
>> access ). Especially if you'll be using this in loops, where the
>> compiler may not be able to move a constant row indexing out of the
>> loop ( if you array wasn't declared doubly restricted, e.g. ).
>>
>> Since your access is going to be array+x*ysize+y or array+y*xsize+x
>> anyway, does it really matter what syntax you use?
>
> Then you just have to ask whether your array is small enough to fit in
> cache (or used in small enough parts to fit in cache), because two
> cache hits is gonna be a lot faster than one cache hit, and a
> multiply.
That's not true at all, since there is a true dependency between the
two loads and lwz is a 2:1 instruction and typically, the multiply is
either partially or fully redundant or a multiplication by an induction
variable while the outer lwz can often not be optimized even if it is
fully redundant.> This is the level at which optimization gains you nothing but
> obfuscated code
As a general statement, this is simply not true. Wether this "level" of
optimization gains you something, and wether it would lead to
obfuscated code, depends entirely upon the context.> - you probably gain 0.001 seconds on one chip and loose the same on a
> different chip...> So stop trying to find that one clock cycle difference it makes and
> start trying to (a) write code that looks nice, and (b) write fast
> algorithms.
I trust everyone to have a sound judgment on when and what to optimize
and when and what not to optimize. Bringing up the "premature
optimization" point everytime someone talks about efficient coding is
redundant at best. Everyone knows their own situation and application
best, so trying to lecture them on what is appropriate for their
situation is simply rude. People are intelligent enough to understand
if a comment were relevant for them or not, don't treat them like
they're not.
Also, if it is never considered OK to discuss what is efficient and
what is inefficient programing - how are we to develop the skills we
need when it *is* important to optimize?
But if you really wanted to bring this up, writing code that looks nice
has very little do to with wether you're writing efficient code or not.
The fastest known algorithm has probably already been selected, or its
design requires deep specialist knowledge of topics very different from
computer programming. Cache-tuning and other optimizations can usually
improve your speed by a rather large integer factor - such as going
from 20 seconds to less than one second to process a large data set.
. . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . .
. <waterspirit...> . . www.synapticpulse.net . -
You should take a look at MathArray:
ftp://ftp.gnustep.org/pub/gnustep/contrib/MathArray.0.70.s.tar.gz
Benoit
On Mar 14, 2005, at 4:19 AM, Daniel Child wrote:> Hi All,
>
> I've run into a situation where it would be great to have a
> multidimensional NSArray or NSMutableArray. Is there such a class? If
> not, any suggestions on the most elegant solution?
>
> Thanks,
> Daniel
>
> _______________________________________________
> Do not post admin requests to the list. They will be ignored.
> Cocoa-dev mailing list (<Cocoa-dev...>)
> Help/Unsubscribe/Update your Subscription:
> http://lists.apple.com/mailman/options/cocoa-dev/<marchant...>
>
> This email sent to <marchant...> -
>> - you probably gain 0.001 seconds on one chip and loose the same onI never said that it wasn't important to optimize or that it wasn't OK
>> a different chip...
>
>> So stop trying to find that one clock cycle difference it makes and
>> start trying to (a) write code that looks nice, and (b) write fast
>> algorithms.
>
> I trust everyone to have a sound judgment on when and what to
> optimize and when and what not to optimize. Bringing up the
> "premature optimization" point everytime someone talks about
> efficient coding is redundant at best. Everyone knows their own
> situation and application best, so trying to lecture them on what is
> appropriate for their situation is simply rude. People are
> intelligent enough to understand if a comment were relevant for them
> or not, don't treat them like they're not.
>
> Also, if it is never considered OK to discuss what is efficient and
> what is inefficient programing - how are we to develop the skills we
> need when it *is* important to optimize?
to discuss optimizations. But what you demonstrated is something that
I would barely count as being in the category of optimizations.
Optimizations are things that bring the complexity of your program
down, not things that gain you a clock cycle here and a clock cycle
there.> But if you really wanted to bring this up, writing code that looksAbsolutely, but eliminating one multiply to go from
> nice has very little do to with wether you're writing efficient code
> or not. The fastest known algorithm has probably already been
> selected, or its design requires deep specialist knowledge of topics
> very different from computer programming. Cache-tuning and other
> optimizations can usually improve your speed by a rather large
> integer factor - such as going from 20 seconds to less than one
> second to process a large data set.
array[x][y];
to
*(array + x * kYSize + y)
is a particularly ugly hack and it is debatable whether it even gains
you anything.
Bob -
2005-03-15 kl. 20.03 skrev Thomas Davie:>>> - you probably gain 0.001 seconds on one chip and loose the same on
>>> a different chip...
>>
>>> So stop trying to find that one clock cycle difference it makes and
>>> start trying to (a) write code that looks nice, and (b) write fast
>>> algorithms.
>>
>> I trust everyone to have a sound judgment on when and what to
>> optimize and when and what not to optimize. Bringing up the
>> "premature optimization" point everytime someone talks about
>> efficient coding is redundant at best. Everyone knows their own
>> situation and application best, so trying to lecture them on what is
>> appropriate for their situation is simply rude. People are
>> intelligent enough to understand if a comment were relevant for them
>> or not, don't treat them like they're not.
>>
>> Also, if it is never considered OK to discuss what is efficient and
>> what is inefficient programing - how are we to develop the skills we
>> need when it *is* important to optimize?
> I never said that it wasn't important to optimize or that it wasn't OK
> to discuss optimizations.
Sorry, you didn't. It's just the general attitude at some lists and
forums that hit me.> But what you demonstrated is something that I would barely count as
> being in the category of optimizations. Optimizations are things that
> bring the complexity of your program down, not things that gain you a
> clock cycle here and a clock cycle there.
After you've done everything you can to reduce your program complexity,
these kinds of optimization are what's left that you can do and may
give significant gains. It's not one thing or the other, one can do
both. Most of the time, there are better things to do but sometimes
it's worth the effort.
In the end, it's all about that clock cycle here and there. They add up.>> But if you really wanted to bring this up, writing code that looks
>> nice has very little do to with wether you're writing efficient code
>> or not. The fastest known algorithm has probably already been
>> selected, or its design requires deep specialist knowledge of topics
>> very different from computer programming. Cache-tuning and other
>> optimizations can usually improve your speed by a rather large
>> integer factor - such as going from 20 seconds to less than one
>> second to process a large data set.
> Absolutely, but eliminating one multiply to go from
> array[x][y];
> to
> *(array + x * kYSize + y)
Make that array[x*ysize+y] , where ysize was a variable.> is a particularly ugly hack and it is debatable whether it even gains
> you anything.
It's not debatable, it's a question for profiling. It's always been a
locally significant gain in my cases. The denser syntax will only be
worth the gain in tight loop nests that are frequently run.
. . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . .
. <waterspirit...> . . www.synapticpulse.net . -
>> I never said that it wasn't important to optimize or that it wasn'tFair enough â my personal take on the subject is... Write the god damn
>> OK to discuss optimizations.
>
> Sorry, you didn't. It's just the general attitude at some lists and
> forums that hit me.
app, ignore optimizations.
When and only when it works, try to run it through the profiler if and
only if it runs slowly on some systems.>> But what you demonstrated is something that I would barely count asWhile I agree to a certain extent, I have never seen a case where this
>> being in the category of optimizations. Optimizations are things
>> that bring the complexity of your program down, not things that gain
>> you a clock cycle here and a clock cycle there.
>
> After you've done everything you can to reduce your program
> complexity, these kinds of optimization are what's left that you can
> do and may give significant gains. It's not one thing or the other,
> one can do both. Most of the time, there are better things to do but
> sometimes it's worth the effort.
>
> In the end, it's all about that clock cycle here and there. They add
> up.
kind of optimization can actually gain you anything significant other
that when you have *massive* data sets â if you get to a nice low-order
(preferably quadratic) polynomial algorithm, the you're likely to gain
much more than sitting there with an exponential algorithm with a very
highly optimized loop body.
But even that is not what I'm really trying to say - what I'm really
trying to convey is that in general the kind of optimization that saves
you a clock cycle here or there is also the kind that makes your code
harder to read. I tend to say that it's better for my code to be
readable and run on 99% of systems than for my code to be totally
unreadable/maintainable and run on 100% of systems.>>> But if you really wanted to bring this up, writing code that looksBut probably not worth as much as getting rid of the tightly nested
>>> nice has very little do to with wether you're writing efficient
>>> code or not. The fastest known algorithm has probably already been
>>> selected, or its design requires deep specialist knowledge of
>>> topics very different from computer programming. Cache-tuning and
>>> other optimizations can usually improve your speed by a rather
>>> large integer factor - such as going from 20 seconds to less than
>>> one second to process a large data set.
>> Absolutely, but eliminating one multiply to go from
>> array[x][y];
>> to
>> *(array + x * kYSize + y)
>
> Make that array[x*ysize+y] , where ysize was a variable.
>
>> is a particularly ugly hack and it is debatable whether it even
>> gains you anything.
>
> It's not debatable, it's a question for profiling. It's always been a
> locally significant gain in my cases. The denser syntax will only be
> worth the gain in tight loop nests that are frequently run.
loops all together and using a better algorithm ;)
Bob -
2005-03-15 kl. 23.33 skrev Thomas Davie:>>> I never said that it wasn't important to optimize or that it wasn't
>>> OK to discuss optimizations.
>>
>> Sorry, you didn't. It's just the general attitude at some lists and
>> forums that hit me.
> Fair enough â my personal take on the subject is... Write the god damn
> app, ignore optimizations.
> When and only when it works, try to run it through the profiler if and
> only if it runs slowly on some systems.
Yes. I agree completely. A slow and usable app is a lot better than a
fast application that never reaches any users.
It also takes less work to first write a correct and inefficient
implementation which is then optimized, than to try to write a highly
efficient implementation from scratch. But data layout is something
that that can be difficult to change later, so it makes sense to think
about it from the onset.>>> But what you demonstrated is something that I would barely count as
>>> being in the category of optimizations. Optimizations are things
>>> that bring the complexity of your program down, not things that gain
>>> you a clock cycle here and a clock cycle there.
>>
>> After you've done everything you can to reduce your program
>> complexity, these kinds of optimization are what's left that you can
>> do and may give significant gains. It's not one thing or the other,
>> one can do both. Most of the time, there are better things to do but
>> sometimes it's worth the effort.
>>
>> In the end, it's all about that clock cycle here and there. They add
>> up.
> While I agree to a certain extent, I have never seen a case where this
> kind of optimization can actually gain you anything significant other
> that when you have *massive* data sets
From my perspective, datasets usually are massive - and what is
limiting the size of the datasets is the speed of the application. A
faster implementation means you can process more data, have higher
quality results, or give more interactive user feedback.> â if you get to a nice low-order (preferably quadratic) polynomial
> algorithm, the you're likely to gain much more than sitting there with
> an exponential algorithm with a very highly optimized loop body.
Yes, unless the lower order algorithm was less suitable to computer
implementation at your datasize. And once you have changed your
algorithm, you're back to lower level optimizations to improve
efficiency further.> But even that is not what I'm really trying to say - what I'm really
> trying to convey is that in general the kind of optimization that
> saves you a clock cycle here or there is also the kind that makes your
> code harder to read. I tend to say that it's better for my code to be
> readable and run on 99% of systems than for my code to be totally
> unreadable/maintainable and run on 100% of systems.
I think there's an important distinction to make here between
high-level application code that is mostly software architectural and
lower level code that actually does the work your app is built around.
In higher level code, clarity is the most important thing, but in lower
level processing speed is critical.
But optimization is not only about making an existing app run faster,
it also provides room to extend the application! This is the best way
to use a faster computer - to give extended visualization and user
feedback, and more robust and intelligent processing.>>>> But if you really wanted to bring this up, writing code that looks
>>>> nice has very little do to with wether you're writing efficient
>>>> code or not. The fastest known algorithm has probably already been
>>>> selected, or its design requires deep specialist knowledge of
>>>> topics very different from computer programming. Cache-tuning and
>>>> other optimizations can usually improve your speed by a rather
>>>> large integer factor - such as going from 20 seconds to less than
>>>> one second to process a large data set.
>>> Absolutely, but eliminating one multiply to go from
>>> array[x][y];
>>> to
>>> *(array + x * kYSize + y)
>>
>> Make that array[x*ysize+y] , where ysize was a variable.
>>
>>> is a particularly ugly hack and it is debatable whether it even
>>> gains you anything.
>>
>> It's not debatable, it's a question for profiling. It's always been a
>> locally significant gain in my cases. The denser syntax will only be
>> worth the gain in tight loop nests that are frequently run.
> But probably not worth as much as getting rid of the tightly nested
> loops all together and using a better algorithm ;)
Of course, but that is often not possible. Generally, you will need at
least one pass over the data. If you can do that, that one remaining
loop nest will still benefit from performance tuning.
If you know the field of your application well you'll usually be using
the best known practical algorithms ( unless it is patented.. ). And
developing better algorithms could be a several year research project,
if it is possible at all.
. . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . .
. <waterspirit...> . . www.synapticpulse.net . -
> While I agree to a certain extent, I have never seen a case where this
> kind of optimization can actually gain you anything significant other
> that when you have *massive* data sets.
Where "massive" is in the eye of the beholder and needs to take *time* into
account.
Whilst I agree in principle, I did encounter a problem a long time ago where
I was set some work by a lecturer to "code in assembler" because he was
convinced that his 2D FFT could never be made fast enough in C. I handed
him back a straight C version that was "too fast" - he had to concentrate on
speeding up other areas in his system to cope.
Unrolling array accesses when you know they are sequential and using
pointers to iterate along them, combined with actually paying attention to
the math you are actually doing in when processing your arrays pays off big
time even in small datasets if you have to visit them over and over.
ie there aren't many gains to be made made by recognising that an array
access could be converted to a pointer dereference - the gains come with
array iteration converted to pointer iteration.
Moral: understand your whole algorithm before you worry about tuning little
bits of it.
Which is just reiterating what others have said. -
2005-03-16 kl. 00.42 skrev Jeff Laing:>> While I agree to a certain extent, I have never seen a case where this
>> kind of optimization can actually gain you anything significant other
>> that when you have *massive* data sets.
>
> Where "massive" is in the eye of the beholder and needs to take *time*
> into
> account.
>
> Whilst I agree in principle, I did encounter a problem a long time ago
> where
> I was set some work by a lecturer to "code in assembler" because he was
> convinced that his 2D FFT could never be made fast enough in C. I
> handed
> him back a straight C version that was "too fast" - he had to
> concentrate on
> speeding up other areas in his system to cope.
>
> Unrolling array accesses when you know they are sequential and using
> pointers to iterate along them, combined with actually paying
> attention to
> the math you are actually doing in when processing your arrays pays
> off big
> time even in small datasets if you have to visit them over and over.
>
> ie there aren't many gains to be made made by recognising that an array
> access could be converted to a pointer dereference - the gains come
> with
> array iteration converted to pointer iteration.
I just have to point out that while this used to be true for older
compilers, it is not generally true today. Most compilers today can
optimize sequential array access better than iterated pointer
arithmetic and dereferencing. Internally, they try to rewrite the
pointer arithmetic/dereferencing to array accesses. Many optimizations
requires good data dependency analysis, which the compiler may have
difficulties doing on pointer arithmetic expressions.
So today, it's more often faster to use array access syntax than
explicit pointer arithmetic. Unless you have special circumstances that
allows you to remove equivalent induction variables or something
similar, it's often better to stick with array syntax.> Moral: understand your whole algorithm before you worry about tuning
> little
> bits of it.
>
> Which is just reiterating what others have said.
. . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . .
. <waterspirit...> . . www.synapticpulse.net . -
On Mar 15, 2005, at 4:33 PM, Pandaa wrote:> Many optimizations requires good data dependency analysis, which the
> compiler may have difficulties doing on pointer arithmetic
> expressions.
Not really.
Did you know that a[b] is the exact equivalent of *(a+b)? Yes, for any
a and b that you could think of.
For example, this rule is why 1[x] compiles and runs just as well as
x[1]. (Yup, it doesâtry it.) Or why you can convert a number to a hex
character with "0123456789ABCDEF"[number].
C is full of clever tricks like this that you should avoid because they
are hard to understand when you look back at your old code a year or
two later :) -
2005-03-16 kl. 01.49 skrev John Stiles:> On Mar 15, 2005, at 4:33 PM, Pandaa wrote:
>
>
> Many optimizations requires good data dependency analysis, which the
> compiler may have difficulties doing on pointer arithmetic
> expressions.
>
> Not really.
Yes, really. Read up on auto vectorization.> Did you know that a[b] is the exact equivalent of *(a+b)? Yes,
> for any a and b that you could think of.
Of course, a[b], b[a], *(a+b) are all equivalent.> For example, this rule is why 1[x] compiles and runs just as well as
> x[1]. (Yup, it doesâtry it.) Or why you can convert a number to a hex
> character with "0123456789ABCDEF"[number].
> C is full of clever tricks like this that you should avoid because
> they are hard to understand when you look back at your old code a year
> or two later :)
. . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . .
. <waterspirit...> . . www.synapticpulse.net . -
On 16 Mar 2005, at 00:33, Pandaa wrote:> I just have to point out that while this used to be true for older
> compilers, it is not generally true today. Most compilers today can
> optimize sequential array access better than iterated pointer
> arithmetic and dereferencing. Internally, they try to rewrite the
> pointer arithmetic/dereferencing to array accesses. Many optimizations
> requires good data dependency analysis, which the compiler may have
> difficulties doing on pointer arithmetic expressions.
Are you sure about this?
"Internally, they try to rewrite the pointer arithmetic/dereferencing
to array accesses."
And what is an 'array access' at assembler level? Have you actually
looked at the code compilers generate for different C idioms or are you
just speculating?
--
Andy Armstrong, hexten.net -
This is no longer strictly directly relevant to Cocoa.
If you have other suggestions for dealing with multidimensional
arrays in Cocoa, please feel free to continue, otherwise please desist.
mmalc -
On Mon, 14 Mar 2005 14:03:44 -0500, Serge Meynard <meynards...> wrote:>> Hi All,
>>
>> I've run into a situation where it would be great to have a
>> multidimensional NSArray or NSMutableArray. Is there such a class? If
>> not, any suggestions on the most elegant solution?
>>
>> Thanks,
>> Daniel
>
> It's actually one of the major annoyances (to me anyway) of working in
> pure Obj-C code on this project: there is no direct support for
> multi-dimensional arrays, or even static arrays of PODs.
I've not used it, but there's a multi-dimensional NSArray-like class
at <http://www.geocities.com/kritter_cocoadev/KTMatrix/>.
-Ken
