One more "strlen" - was: Note to Chuck Crayne

Evenbit wrote: 
Frank Kotler wrote:

True. Caused me to make an interesting observation, though... If *you*
optimize strlen to shave one cycle off it, and you distribute your
library to 1000 users, and they each write a program that uses strlen
1000 times, and distribute it to 1000 end-users, and they each run it
1000 times... that's a hell of a lot of cycles!


But that is spread-out over a bunch of machines and a bunch of time --
how much time is being saved compared to how much time all those
machines spend being idle?

Sure it's "spread out", but it's still a lot of "end-user time" being saved/wasted from an "insignificant" per-call difference. I don't see that the amount/percentage of time the machine sits idle is relevant.

Under what conditions are you likely to be
calling a STRLEN function 1000 times in a row?

Very few, hopefully. I think we're agreed that the fastest (and shortest!) way to do strlen is to not do it at all. First, we have to imagine that we don't have any choice of data format - zero-terminated strings are being forced on us. Betov points out that "EditBox" gives us the length - same is true of "sys_read" - so we have to imagine that's not the case. We would of course only do strlen once per string (how best to store it?), so we have to imagine we've got a lot of strings being thrown at us. Then, why do we need the length? Presumably, we've got to do some "processing" of these strings... would it make sense to "interleave" the end-of-string test with other processing, rather than calculate it separately? Only if we can rule out the "don't do it at all" option do we need to think about a fast strlen. Still, we might need to do it sometime...

As usual, "what are you going to do with it" determines what's "good" or
"worthwhile".

Indeed. 

Indead, even! :)

There must be "even worse" in common usage. As you know, I like "open
sauce" software, so if I felt like plowing through the C source, I cou;d
find a real gem for us to optimize. When I click on the little
hieroglyph to "sort by thread" instead of "sort by date", it takes - by
wall clock - approximately a minute and fifteen seconds to complete.
What kind of a sort algo does *that*???

Perhaps that isn't an algo problem but a program design problem?

Almost certainly true. Unlikely to be helped by the (allegorical) difference between "scasb" and some high-tech sse3 instruction.

Why
is the program waitting for the user to click the glyph {the 'qoute
balloon' in Thunderbird I presume?}


Yeah... looks a little like a cartoon "speech balloon", I guess.

to run a sort algo to re-order the
messages?  A better approach would be to keep a running index table for
every column the user can sort by and every index table should be
updated every time Thunderbird recieves an email/post...this way, the
click on the glyph merrly selects which index table to use when picking
what message headings to show in the window -- no need to run no
freak'n algo.

That sounds like it would work well. I suppose we could argue that all that indexing is "wasted" if the user *doesn't* use it. Even if we wait for "on demand" to do our sorting, it ought to go along a little faster than that.

Disclaimer: I'm complaining about software that is *not* the latest version, running on hardware that's a little underpowered for the task.

"Optimizing strlen" is not going to solve this type of problem, but
getting rid of the "it doesn't matter" attitude might...


This attitude change also goes for the over-all program design... and
in most cases, is where it is more important than at the algo level.

Right. I don't think of the "algo level" as being just a single level - overall program design is an "algorithm", too, in my mind - but I agree. The overall design needs the "I must use the fastest instruction" mindset. Simply replacing slower instructions with faster ones isn't going to help much. Replacing "bubble sort" with "qsort" probably isn't going to be enough, either. The problem is at a "higher level" than that, I'm quite sure. I mentioned it only as an example that the "any old thing is good enough" rule, if consistantly applied, really *does* result in stuff that's "too slow" sometimes.

Best,
Frank
.

Relevant Pages

  • Re: A truely BIJECTIVE BWT is here!
    ... Each cycle in my way is unique. ... Given strings from ... separte cycles are different the compare function need only ... You could sort each cycle indepently and then merge the results ...
    (comp.compression)
  • Re: Solution for sorting an array alpha-numerically
    ... strings up into groups and sorting the groups seperately, ... > so that numeric and alphabetic data sort as seperate groups. ... To the same project as the web page, add the class AlphaNumCompare() ...
    (microsoft.public.dotnet.general)
  • Re: Friend got a new one
    ... packing under the saddle to raise the action, that sort of thing can really ... Lugged it home, removed the mossy strings, ... I have had 'dog' Martins through the shop over the years, ...
    (rec.music.makers.guitar.acoustic)
  • Re: Unwarranted aggression and discrimination towards cyclists
    ... On 18 February Dave the Handyman posted the following, ... cycle without being subjected to this sort of abuse. ... Could you give us a report on these interviews please, you know the sort ... Cut out the sin ...
    (uk.rec.cycling)
  • Re: a question for sorting keys in Map
    ... I have a Map, actually a TreeMap, which will automatically sort the keys ... You can write your own Comparator object which implements the Compare ... strings so that X10 comes after X2 instead of before it. ... Unix ls command sort file names the way you want your strings to sort. ...
    (comp.lang.java.programmer)