Re: Reading and writing a big file in Ada (GNAT) on Windows XP

(I've been on vacation and just am now catching up...)

"Markus E Leypold"
<development-2006-8ecbb5cc8aREMOVETHIS@xxxxxxxxxxxxxxxxxxxxx> wrote in
message news:9qhcqr5gfi.fsf@xxxxxxxxxxxxxxxxxxxxxxxxx
Adam Beneschan <adam@xxxxxxxxxx> writes:

On May 3, 5:28 pm, Markus E Leypold
<development-2006-8ecbb5cc8aREMOVET...@xxxxxxxxxxxxxxxxxxxxx> wrote:
"Randy Brukardt" <r...@xxxxxxxxxxxxxx> writes:
"Adam Beneschan" <a...@xxxxxxxxxx> wrote in message
news:1178224048.034635.39010@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
...
It strikes me that Index is the kind of function that really ought
to
be written in assembly language, at least partially. I notice that
the version of Linux that I'm using has a built-in function to
search
memory for a substring; this is very descriptively called memmem()
and
has the amusing profile

void *memmem (const void *needle, size_t needlelen,
const void *haystack, size_t
haystacklen);

according to the man page. But I assume this is written to use
registers optimally and take advantage of the REP instructions (on
an
x86 or Pentium). I don't know how GNAT implements Index---I haven't
looked into it.

The big expense in Index is the mapping set or function, not the
actual
compare. For Janus/Ada, I had seen a similar problem (a big deal as
Index
was used to look for spam patterns), and finally special-cased a
number of
common cases (no mapping, single character patterns, and so on). I
also
spent a bit of time on the code generator, figuring that this sort of
string
manipulation code is common enough that it might as well be generated
well.
The updates helped a lot, although they don't quite generate a single
instruction such as is possible. (OTOH, Intel used to recommend
avoiding the
block move and compare instructions because they fouled up the
pipeline and
thus slowed the overall execution. I don't know if that is still
true, but
ifi it is, there might be less benefit to hand-coded assembler than
you are
thinking...)

I'd like to add, that some years ago I read a rather well written
paper about this kind of text searches. Just repeating comparisons in
two loops (one to move the offset in haystack, the other to compare
need against haystack+offset) is actually not the best method. I.e. if
one fails when comparing this

haystack: ... asjkajkaewudajksdkwueqeqweadasdqw3adkadkakd
needle: adasdqwsdfklsdf
^
comparison fails

one can immediately increase the offset by 7, since the needle does
not contain a '3' in the part that is before the point where the
comparison failed. The technique I read about, used considerations of
this kind to compile the 'needle' into some automaton which could skip
more than 1 character at a time in haystack and then executed /
interpreted this automaton. (Actually the algorithm was a bit more
tricky than this, I think: If the automaton sees a character that is
not in needle at all, it can immediately skip for the length of needle
and I think part of the trick was to start comparing from the end of
needle).

So in this case a better algorithm is probably the way to go (and I
agree, asembler and REP, which would just be the naive algorithm with
2 loops, won't cut it, at least I'd not bet on it)

A big problem, however, is that while such "well-written" papers may
be mathematically correct, they must make assumptions that aren't
necessarily true in real life. For instance, analyses that I've read

While that is certainly true, I don't think it applies in this case,
The algorithm I'm referring to, and which I'm to lazy to look up,
seems to be rather much in use when looking for a give substring in a
larger string/text, like when searching or searching/replacing in a
text editor.

No, Adam is right, it applies in every case. A brute force search is often
cheaper than a fancier one. For instance, in the Janus/Ada parser, I
implemented a fancy binary table search in order to find items faster. It
actually made things slower. The problem was that many of the table rows
only had a few items, so the setup time (which required a number of adds and
shifts) took longer than a brute-force search (which was just a simple for
loop, one add per iteration). Hand coding that loop in assembler turned it
into a handful of instructions.

Brute force is almost always going to be better if the comparisons are cheap
and you can keep everything in registers. That's often true for Index.

....
Originally I intended to point people, who try to find substrings to
the fact that there a much smarter algorithms available which can skip
a significant percentage of character comparisons. Wether this is
faster than brute force dumb comparison would have to be decided in
any single case. Ideally though, in the case of a substring of N
characters, when a single character comparison fails, offset can be
skipped by a K in the order of magnitude of N, that is, if you look
for a substring of N characters, you might only have to do something
on the order of 1/N of the comparisons you'd have to do in the dumb
implementation. Admittedly things are more complicated than that, but
I think one can see, that the point where it becomes as fast as the
dumb case could be reached for small N, esp. if the interpreter is
handwritten assembler or generated by a really good code generator.

Here the problem is that you have to know something about N in order to
tell. My experience is that N is usually small (often 1), and in such cases
there is likely no value to a fancy algorithm. Of course, in a general
routine like Index, pretty much anything can happen, and it is highly
unlikely that the algorithm will be optimal for every possible case.

Truth is, this demonstrates a standard moral of programming: its fine to
write your programs with a standard library routine, but you need to profile
it after doing so to see where the bottlenecks are. And if you're going to
call anything (but especially some canned library routine) millions of
times, you need to be prepared to replace it with one that is optimal for
your application. In this case, for instance, you can figure out the
distribution of N for a particular program, and implement an appropriate
algorithm. You can't expect us compiler writers to do it for you; we may
have a very different distribution of N in mind. (Of course, if the routine
isn't critical, don't sweat it -- doing otherwise is just premature
optimization.)

Randy.


.

Relevant Pages

  • Re: Reading and writing a big file in Ada (GNAT) on Windows XP
    ... memory for a substring; this is very descriptively called memmemand ... common cases (no mapping, single character patterns, and so on). ... So in this case a better algorithm is probably the way to go (and I ... the source length is>M and the pattern length is>N, ...
    (comp.lang.ada)
  • Re: Regular Expression for validating a url field
    ... (Do not use the tab character for indentation, ... against a supposed string value, and since you do not do perform a strict ... If x is NaN, return false. ... `false' is returned to the calling algorithm, ...
    (comp.lang.javascript)
  • Re: Paper & pencil password algorithm
    ... but I have to try to find an algorithm ... need for algorithmic passwords is rather great and increasingly urgent, ... I would look at bigger character sets and here are the results. ... There are other uses for these bases, 66 is good for a stream cipher, ...
    (sci.crypt)
  • Re: Question about bit strength
    ... Make good guesses about strength of an encryption soultion is not very ... The algorithms used to derive the key and for actual encryption process ... algorithm is at most equal to the number of steps needed to break it; ... method 2 using every character in the bit range bar the first 15. ...
    (sci.crypt)
  • Re: Implementing strstr
    ... >> The proper way to implement strstr is to make a DFA of needle, ... >> algorithm. ... > amount of setup required before you start searching. ... fixes many of the shortcomings of Windows 98 SE". ...
    (comp.programming)