Subject: RE: [hackers-il] Do Faster Computers Imply Slower Code?

From: Chen Shapira <[email-masked]>
Date: Fri, 31 May 2002 19:36:15 +0200

Hi,

From my humble experience, smart algorithms and data-structures are usually
the easier part of efficiency. They are also the most fun. Enjoyable like
any good riddle. 
From the algorithmic point of view, my code is usually quite efficient the
first time around.

The difficult part comes when using the best algorithms isn't good enough. 
Somewhere at that point you start going into the bits and pieces:
Am I copying data by mistake? Is STL copying data behind my back?
The type conversions are costing me time.
Which functions should be inlined? Which variable should be "register"?
Simplifying the design, that factory may be cool but it slows things down.
Is there a better way to handle the threads? Should I cache the DB
connections? (The DB question isn't trivial, ADO does its own caching and in
some cases its better)
DB optimisations - a full world of its own. Locks, indexes, queries etc. 

My code is pretty decent algorithm wise and thanks to my DBA, all work with
the DB is optimised like hell.
The rest of the stuff? I only do it when I must. I don't enjoy nitpicking my
functions with profiler.
Thanks to fast computers and patient users, I'm not forced into this mess
too often.

Thanks,
Chen.

---

From: "Ofir Carny" <[email-masked]>
Date: Sun, 2 Jun 2002 15:07:59 +0200

It was over a year ago, so my memory is not that clear, but see:

http://www.sgi.com/tech/stl/Container.html
"For many containers, such as vector and deque, size is O(1). This satisfies the requirement that it be O(N)."

The fact that this line is so hard to find in the specs is another problem.

I am pretty sure that what I saw there was clearer about the O(1) recommendation, it might have changed since though.

But this is beside the point, the point is the inherent problem in using a library whose algorithmic basis radically changes
between different implementations.

-----Original Message-----
From: Chen Shapira [mailto:[email-masked]]
Sent: Sunday, June 02, 2002 2:28 PM
To: [email-masked]'
Subject: RE: [hackers-il] Do Faster Computers Imply Slower Code?

> The STL specification recommends (I think the word it uses is 
> 'should') an O(1) implementation, MS do have a good reason for 
> their choice, but as long as different implementations use 
> different algorithms, STL code is not portable, at least 
> performance-wise.

1. Checking the specification here:
http://www.sgi.com/tech/stl/index.html
The only complexity specification on Deque there, is the same one on a
container. That is - linear in the number of elements.
So it actually is standard, but less efficient than other implementation.
You were counting on a non-standard feature.

2. I have no pointer here, but AFAIK, they actually compute the size of
deque by pointer arithmethics.
They keep the deque in several fixed size arrays, and they go over those
arrays. Its still O(n), but not as silly as going over all the elements.

To unsubscribe from this group, send an email to:
[email-masked]

Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/

*
 *******************************************************
This email has been scanned by Port Authority.

********************************************************

---

From: "Ofir Carny" <[email-masked]>
Date: Sun, 2 Jun 2002 15:21:36 +0200

Repling to myself:

The docuemnt to look at is the the ISO standard. Here is the official excuse I was refering to:

"This choice is permitted by the C++ standard. The standard says that size() "should" be constant time, and "should" does not mean the same thing as "shall". This is the officially recommended ISO wording for saying that an implementation is supposed to do something unless there is a good reason not to. "

-----Original Message-----
From: Chen Shapira [mailto:[email-masked]]
Sent: Sunday, June 02, 2002 2:28 PM
To: [email-masked]'
Subject: RE: [hackers-il] Do Faster Computers Imply Slower Code?

*

---

From: Chen Shapira <[email-masked]>
Date: Sun, 2 Jun 2002 15:47:02 +0200

I see your point.

I'll just mention that the excuse is from SGI's FAQ.
This means that both SGI and MS prefered not to use the extra variable, but
calculate the size directly.
Those are 2 of the 4 large and common implementations of STL. (The other two
are ObjectSpace and STLPort, and I'm not sure what they did). So if its both
standard conforming and damn common - it should have probably been expected.
In anycase, never again will I count on O(1) performance in Deque::size.

> From: Ofir Carny [mailto:[email-masked]]
> Sent: Sunday, June 02, 2002 3:22 PM
> "This choice is permitted by the C++ standard. The standard 
> says that size() "should" be constant time, and "should" does 
> not mean the same thing as "shall". This is the officially 
> recommended ISO wording for saying that an implementation is 
> supposed to do something unless there is a good reason not to. "
> 
> "For many containers, such as vector and deque, size is O(1). 
> This satisfies the requirement that it be O(N)."
> 
> I am pretty sure that what I saw there was clearer about the 
> O(1) recommendation, it might have changed since though.
> 
> But this is beside the point, the point is the inherent 
> problem in using a library whose algorithmic basis radically changes
> ------------------------ Yahoo! Groups Sponsor 
> ---------------------~-->
> Tied to your PC? Cut Loose and
> Stay connected with Yahoo! Mobile
> http://us.click.yahoo.com/QBCcSD/o1CEAA/sXBHAA/saFolB/TM
> --------------------------------------------------------------
> -------~->
>