Re: asm grep

Robert Redelmeier wrote:

....
Did anyone mention using the Boyer-Moore skip search algorithm
(wiki & elsewhere)?

I don't think it's been mentioned in this thread. I'm "aware" of Boyer-Moore, but I'd have to read up on it before attempting to implement it...

If speed is important, first get the best
algorithm!

Right! A crappy algorithm implemented with the fastest possible instructions is still crappy code.

If size is important, then it's hard to beat the slow,
un-hardware-optimized REP / CMPSB .

Yeah... but "rep cmpsb" can be used more or less efficiently, too...

We're in a funny situation... we can worry about whether "rep cmpsb" is hardware optimized or not, but in between the lightning-fast (or dog slow) instructions, we're calling the OS... which tends to be on the "canine" side... So a program which minimizes calls to the OS, but does so using "slow" instructions, is likely to be much faster than a program which calls the OS often, but uses "fast" instructions to do so.

For simple reads I doubt the MMX tricks or cache blocking used in
bcopy() help much. But you can always try blocking REP/CMPSB into
MMU burstsize chunks and headed by multistride PREFETCH or dummy loads.

Yeah... I think we need to worry about that last, though. Before that, probably a better search algorithm - probably Boyer-Moore - and before *that*, quit reading the file a byte at a time!!!

The asmutils concern themselves strictly with size. As I mentioned to Rod, I think we can make this not-quite-so-painfully-slow, without adding "too much" to the size.

I also complained that the speed was horrible. The issue is *exactly* the example Robert cited - "sys_read ebp, tmp, 1" - we're calling the OS for every byte. If the "C newbie" did the same, he'd be slow too, but he probably knows fread() and/or fgetc()... may not know that read() exists. These do the buffering for him, so he's probably gonna kick our ass!

Exactly. Getting to the unbuffered versions in C is not a newbie skill.

Right. Whereas an asm newbie... may not realize that he wants buffering, but hopefully he'll soon learn.

(I should make it clear I'm not calling Konstantin, or other asmutil authors, "newbies"! The asmutils "are what they are". I think maybe they may have "gone too far" in this case.)

Best,
Frank
.

Relevant Pages