Re: [OT] Premature optimizations (was: Where is NSList?)
Re: [OT] Premature optimizations (was: Where is NSList?)
- Subject: Re: [OT] Premature optimizations (was: Where is NSList?)
- From: Stephen Checkoway <email@hidden>
- Date: Thu, 29 Jul 2004 13:25:55 -0700 (PDT)
On Thu, 29 Jul 2004, Allan Odgaard wrote:
>
> Programmers are notorious for optimizing the wrong code.
>
>
What is your basis for that statement? which programmers are you
>
referring to?
My basis is that I have done similar things myself and I have watched
others do it. Not only that, but I have read nearly identical assertions
in nearly every single textbook I have that deals with programming (as
opposed to the strictly theory books--I'd say that only half of those
mention it).
>
>
> The pervious point was well made and perfectly valid.
>
>
I disagree. If you understand time complexity, you mostly do not need
>
to profile your code to know how well it scales, and if you have
>
reusable data structures, you do not need to spend extra time making it
>
right from the start, rather than fix it when users complain that the
>
app is useless for larger quantities of data, or just ignore the
>
problem, which seems to be the case for half the apps I use... ;)
You disagree that the point was valid? I do understand time complexity
(read my just submitted post on this very topic). I know that it is used
for a first approximation (read my examples at the very end of the other
post).
I will be the first to agree that the use of the correct data structure is
essential. There is no reason to use a treap (yes, a treap) when you need
a hash table.
However, many times people will start optimizing every piece of code in
sight, not realizing that the real bottle neck is somewhere totally
different (in another thread perhaps) and they are making little or no
difference in the running time.
As an example, how about we consider a list of windows on screen. Lets say
that we want to keep the list sorted and we want to be able to add new
windows in the middle of the list. Now lets assume that each window has
one of those fancy glowing buttons that makes Cocoa apps so pretty. Now if
you decide to be super efficient, you spend your time making the perfect
data structure for this (because, lets face it, you want this to scale
nicely to any number of windows and insertion into an array would be
really slow (O(n)). So now you've spent your time getting (or writing) the
perfect data structure for the task and since you know the time
complexity, you're all set.
Except that for a few windows the time difference between copying 10
entries in an array to make room for a new one is more or less the same as
just allocating a new node to insert into your data structure. That's all
well and good except that what happens if we have 1000 windows and we want
to delete one. Now I bet you are happy you have your data structure which
can do this super efficiently (I know I would be). But lets think about
what we're talking about here. 1000 windows all with pulsating buttons
needing to be updated at once. There was a post on this list a few days
ago about how adding one button caused the processor usage to skyrocket.
Now consider having 1000 of these. Is it really going to matter that it
took a full second to copy 500 of those entries (on average) to delete
that one entry. A second is most likely far longer than it would really
take, but for the sake of argument, lets stick with 1. Your application is
so unresponsive already that it takes seconds for a single click to even
register anyway that the second you shaved by the efficient data structure
means nothing.
>
We have a lot of people which program whom doesn't have in depth
>
knowledge about data structures and time complexity, and I think it's a
>
disservice to these to almost label optimizations as a bad thing. What
>
we could preach is how to do proper optimizations, and choosing the
>
proper data structure is the first step, which was all the OP wanted...
Optimizing the wrong thing is bad. I agree, choosing the correct data
structure is an essential first step. The OP's question had been answered
many times already, the topic had moved on by the time I wrote that last
reply.
- Steve
_______________________________________________
cocoa-dev mailing list | email@hidden
Help/Unsubscribe/Archives:
http://www.lists.apple.com/mailman/listinfo/cocoa-dev
Do not post admin requests to the list. They will be ignored.