Re: improve strlen


jukka@xxxxxxxxxxxx wrote:
> Hello. Your latest optimizations make the assembly version _slower_
> than the C++ version here. The original code was ~6% faster, now it is
> ~15% slower.
>
> Unrolling like that kinda kills branch prediction, I suppose. And burns
> code/tracecache for no real gain..

Unrolling code won't *kill* branch prediction; it might not take
advantage of branch prediction, but it doesn't kill it (i.e., make it
less effective when it is used).

Of course, the main problem I'm seeing here is that people are running
their programs and measuring the results on different CPUs. And all
bets are off when you do that. This is why it's almost a worthless
exercise to "count cycles" these days. If you optimize the code on one
CPU, chances are pretty good it *won't* be optimal on a different CPU.
So unless you're writing the code to run on a specific rev of a
specific CPU, shaving one or two clock cycles off the execution time of
an algorithm is a real waste of time.

While I can appreciate why it would be nice to have the world's fastest
strlen program, given the effort that seems to be put into this problem
over and over again, the more reasonable question to ask is "why aren't
all these people using a better data structure that makes string
operations more efficient?" (e.g., including the length as part of the
string data type; maybe reference counters, too). Sure, we'd all love
the idea of simply recompiling old programs that don't know any better
and having them run faster, but the truth is that if people would
simply stop using zstrings (except for interface with OSes and other
code that uses them) and employ a better internal data structure, the
whole issue of the "fastest strlen" algorithm would go away. If people
would use reference counters and pointers, then worrying about the
"fastest block move operation" would diminish, too.

As the old saying goes - get the algorithm (and, presumably, data
structure) right *FIRST*.
Cheers,
Randy Hyde

.

Relevant Pages

  • Re: workqueue deadlock
    ... but it is still preemptible and the lock is specific. ... preempt_disableis the preferred way of holding off cpu hotplug. ... already (and can be programmatically attached to the data structure ... "CPU hotplug code" is the implementation of that data structure, ...
    (Linux-Kernel)
  • Re: speed problems on laptop [SOLVED]
    ... > - Generally X performance seems slower. ... and ran the CPU a lot slower in the bargain. ... I unstuck the cooling fan and installed i8kmon; ...
    (Debian-User)
  • [patch] Real-Time Preemption, -RT-2.6.12-rc1-V0.7.41-07
    ... >> is not a guarantee to have the data structure, the read lock has to be ... it's along the lines of Esben's patch, but with the conceptual bug fixed ... another CPU, so that current->rcu_data is that of another CPU's. ... so when a preemption-off section ...
    (Linux-Kernel)
  • Re: Best way to read from directory with many files
    ... If you're CPU bound, then you can either partition the work ahead of time, handing a complete list of files to process to each thread before they start. ... The former is better if you expect the actual processing to be quick and having many threads consuming from the same data structure would create too much contention to allow the algorithm to scale well. ... If for some reason you find that using Directory.GetFilesis in fact simply taking too much of a memory hit and hurting performance, I think you'll have to use the unmanaged API through p/invoke. ...
    (microsoft.public.dotnet.framework)
  • Re: SATA-controller for Linux (Slackware)?
    ... It's not uncommon for hardware RAID-5 to be slower than software RAID-5 ... even the fastest RAID cards I've ... seen only have about a 600MHz CPU. ...
    (comp.os.linux.hardware)