mainHybrid Self-Tuning Boyer-Moore - Summary

Membership Info
Project Admin:
1 active member

Group identification
Id: #11394
System Name: hstbm
Name: Hybrid Self-Tuning Boyer-Moore
Group Type: non-GNU software and documentation

Search in this Group


This project is not part of the GNU Project.

Introducing hstbm, an "exploratory fork" of GNU Grep.

GNU Grep is an industrial-strength text search program, and aspires to be the "Fastest Grep in the West (we hope)". Grep is one of the cornerstone utilities in Unix, and the GNU implementation has a stunning set of achievements under its belt:

  • Sustained time as a production-quality system utility (decades);
  • Different search algorithms (POSIX Regex, the Deterministic Finite-State Matcher, Keyword-Set matcher, Boyer-Moore-family "sublinear" string searches, Perl regular expression matcher, and also hardware-specific opcodes);
  • Platform and OS support, including POSIX, Windows, and others; and
  • Internationalisation and localisation support (including Unicode).

I strayed into the regular expression search field almost by accident, after noticing that the 4-byte x86 assembly sequence "lodsb; xlat; jmp ax" led to a compact finite-state machine that could use threaded code in a 256-byte code page. This led to the publication of the article "High-Speed Finite-State Machines" in the November 1997 edition of Dr. Dobb's Journal. I presented 3 examples of the state machine in action:
1. A word count utility;
2. A non-deterministic regular expression match program; and
3. A table-driven static Huffman bitstream decoder.

That regular expression search code (Grouse Grep) had some strengths and weaknesses; in some cases, it was faster than any other Grep program available to me, due to optimisations easy to see because of the table-based search layout. My inexperience in big-iron systems (coming from an embedded-systems and microprocessor background) showed in some other areas, however: The code was very slow in MMU-based OSes, as it edited the file search buffer with NULs as end-of-line markers, and so was punished with copy-on-write page swapping.

For many, many years, I've wanted to incorporate the worthwhile bits of my code into GNU Grep, but circumstances have been against me at various levels. Part of the problem is that the existing infrastructure in GNU Grep slices and dices (lexes and parses) the pattern quite extensively in order to correctly model some of the more sophisticated search capabilities, but then has to reverse-engineer simple strings (the "musts") back out of the derived representation. Some opportunities for optimisations become harder to identify as a result of this process.

So, in the last couple of years, I've been submitting a Lua script, "untangle", that tries to refactor the slicing and dicing into a more modular design, hopefully allowing the code to capture the raw pattern and model relationships more directly, leading to less need for reverse-engineering, and ultimately hopefully making it easier to identify optimisation cases. This has been looking at pattern handling from a "bottom-up" angle.

The "untangle" script's development, however, has reached a plateau without generating much enthusiasm from others. So this project, hstbm, is the converse: A "top-down" approach to a GNU Grep-like framework, hosting a demonstration algorithm, hstbm (Boyer-Moore-family "sublinear" string searching) that hopes to provide a fairly simple, modular and friendly workbench for developers to experiment with program components.

The code chooses to support only a pared-down version of GNU Grep, so that the code is more streamlined and, hopefully, is easier to evaluate and manipulate.

Registration Date: Mon 19 Jan 2015 03:55:19 AM UTC
License: GNU General Public License v3 or later
Development Status: 3 - Alpha


Latest News rss feed

Communication Tools
 Tech Support Manager (open items: 0, total: 0)
  - Browse open items
  - Submit a new item
 Mailing Lists (0 public mailing lists)

Development Tools
 Bug Tracker (open items: 0, total: 0)
  - Browse open items
  - Submit a new item
 Task Manager (open items: 0, total: 0)
  - Browse open items
  - Submit a new item

Back to the top

Powered by Savane 3.3