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

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

STL has more performance problems than just lazy developers: If I remember correctly, I once used an STL list for a queue, in  code developed on GNU/Linux, and used the size() method, this works great as long as you don't use MS implementation which 
instead of using a variable, actually counts the nodes in the list... I then ported to MS Windows...

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.

	Ofir

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

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

---

From: Shlomi Fish <[email-masked]>
Date: Sun, 2 Jun 2002 13:43:10 +0300 (IDT)

On Sun, 2 Jun 2002, Ofir Carny wrote:

> STL has more performance problems than just lazy developers: If I remember
> correctly, I once used an STL list for a queue, in  code developed on
> GNU/Linux, and used the size() method, this works great as long as you
> don't use MS implementation which

Gee, O(n) linked list length? What's next: arrays implemented as linked
lists? Oh wait, they did that:

http://groups.yahoo.com/group/hackers-il/message/433

> their choice, but as long as different implementations use different algorithms, STL code is not portable, at least

Sometimes, I am amazed at how APIs can have a brain-dead design. I think
when you call a function you expect it to have a reasonable time order of
growth. You do agree that O(n) list length and O(n) array lookup times are
un acceptable? Also, the glib's hash and binary tree comparison functions
do not accept context arguments. (not to mention qsort() and bsearch())
Guy Keren suggested I use a thread-local storage with them...

Are there any guidelines beside that, that you think API vendors should
follow?

Regards,

	Shlomi Fish

> 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/
>
>

----------------------------------------------------------------------
Shlomi Fish        [email-masked]
Home Page:         http://t2.technion.ac.il/~shlomif/
Home E-mail:       [email-masked]

"Let's suppose you have a table with 2^n cups..."
"Wait a second - is n a natural number?"

---

From: Oleg Goldshmidt <[email-masked]>
Date: 02 Jun 2002 20:47:58 +0300

Shlomi Fish <[email-masked]> writes:

> Sometimes, I am amazed at how APIs can have a brain-dead design. 

This is not an API issue, it is an issue of the underlying data
structure and/or algorithms.

> I think when you call a function you expect it to have a reasonable
> time order of growth.

Putting your faith in the implementor.

> You do agree that O(n) list length and O(n) array lookup times are
> un acceptable? 

Lists usually have O(n) length methods (this is a lisper talking). You
should use data structures that are suitable for your problem - that
is why there are both arrays and lists, in particular.

Note that the M$ STL problem alluded to was with queue, not
list. Standard algorithms tests do not suggest using lists for queue
implementations, AFAIK.

-- 
Oleg Goldshmidt | [email-masked] 
"A sense of the fundamental decencies is parceled out unequally at birth."