19 ms·

Thank you for the report! Here’s what I changed: 1. Always use the raw bad_char_table[text[i + pattern_len‑1]] shift—no extra lowercase lookup at runtime. 2. A

Thank you for the report! Here’s what I changed: 1. Always use the raw bad_char_table[text[i + pattern_len‑1]] shift—no extra lowercase lookup at runtime. 2. After a full match, advance by that same table shift instead of just doing i++, so you never miss overlapping occurrences. 3. Removed the “if shift==0 then shift=1” guard—since we build the table excluding the last pattern byte, zero shifts can’t occur. https://github.com/davidesantangelo/krep/releases/tag/v1.0.6 https://github.com/davidesantangelo/krep/releases/tag/v1.0.6

MattPalmer1086 1y ago
Looks better! A couple of other minor comments, since I'm looking at it: 1. You don't need to assign the last char of the pattern inside the search loop every time around the loop. It will never change (line 1143). Just do it once before the search loop starts. 2. tc_last is the text aligned with the end of the pattern window (line 1142). You don't need to get it again when getting the shift (lines 1201, 1208). bad char is the last char which you already have.
- daviducolo 1y ago
  I have applied your suggestions. Thank you again. https://github.com/davidesantangelo/krep/releases/tag/v1.1.1 https://github.com/davidesantangelo/krep/releases/tag/v1.1.1
  - MattPalmer1086 1y ago
    No problem, hope it was useful. I've found a lot of real world performance comes from doing as little as possible inside the main search loop. UPDATE: It's often the case that a simpler algorithm outperforms a theoretically better one. For example, you are using Boyer Moore Horspool, which is the simpler cousin of the original Boyer Moore. BM can get better shifts than Horspool, but it's often slower in practice.
  - MattPalmer1086 1y ago
    An implication of doing as little as possible in the loop is you could boost performance by creating variants of the search algorithm for different types of search. Then you won't incur the penalty or constantly testing "if it's this kind of search do this else do that" inside the search loop.

MattPalmer1086 1y ago

Looks better! A couple of other minor comments, since I'm looking at it: 1. You don't need to assign the last char of the pattern inside the search loop every time around the loop. It will never change (line 1143). Just do it once before the search loop starts. 2. tc_last is the text aligned with the end of the pattern window (line 1142). You don't need to get it again when getting the shift (lines 1201, 1208). bad char is the last char which you already have.

daviducolo 1y ago
I have applied your suggestions. Thank you again. https://github.com/davidesantangelo/krep/releases/tag/v1.1.1 https://github.com/davidesantangelo/krep/releases/tag/v1.1.1
- MattPalmer1086 1y ago
  No problem, hope it was useful. I've found a lot of real world performance comes from doing as little as possible inside the main search loop. UPDATE: It's often the case that a simpler algorithm outperforms a theoretically better one. For example, you are using Boyer Moore Horspool, which is the simpler cousin of the original Boyer Moore. BM can get better shifts than Horspool, but it's often slower in practice.
- MattPalmer1086 1y ago
  An implication of doing as little as possible in the loop is you could boost performance by creating variants of the search algorithm for different types of search. Then you won't incur the penalty or constantly testing "if it's this kind of search do this else do that" inside the search loop.