title: Optimizing a word parser
body: <p><strong>Context:</strong></p>
  
  <p>I have a code/text editor than I'm trying to optimize. Currently, the bottleneck of the program is the language parser than scans all the keywords (there is more than one, but they're written generally the same).</p>
  
  <p>On my computer, the the editor delays on files around <code>1,000,000</code> lines of code. On lower-end computers, like Raspberry Pi, the delay starts happening much sooner (I don't remember exactly, but I think around <code>10,000</code> lines of code). And although I've never quite seen documents larger than <code>1,000,000</code> lines of code, I'm sure that they're there and I want my program to be able to edit them.</p>
  
  <p><strong>Question:</strong></p>
  
  <p>This leads me to the question: <em>what's the fastest way to scan for a list of words within large, dynamic string?</em></p>
  
  <p>Here's some information that may affect the design of the algorithm:</p>
  
  <ol>
  <li>the keywords</li>
  <li>qualifying characters allowed to be part of a keyword, (I call them qualifiers)</li>
  <li>the large string</li>
  </ol>
  
  <p><strong>Bottleneck-solution:</strong></p>
  
  <p>This is (roughly) the method I'm currently using to parse strings:</p>
  
  <pre><code>// this is just an example, not an excerpt
  // I haven't compiled this, I'm just writing it to
  // illustrate how I'm currently parsing strings
  
  struct tokens * scantokens (char * string, char ** tokens, int tcount){
  
      int result = 0;
      struct tokens * tks = tokens_init ();
  
      for (int i = 0; string[i]; i++){
  
          // qualifiers for C are: a-z, A-Z, 0-9, and underscore
          // if it isn't a qualifier, skip it
  
          while (isnotqualifier (string[i])) i++;
  
          for (int j = 0; j &lt; tcount; j++){
  
              // returns 0 for no match
              // returns the length of the keyword if they match
              result = string_compare (&amp;string[i], tokens[j]);
  
              if (result &gt; 0){ // if the string matches
                  token_push (tks, i, i + result); // add the token
                  // token_push (data_struct, where_it_begins, where_it_ends)
                  break;
              }
          }
  
          if (result &gt; 0){
              i += result;
          } else {
              // skip to the next non-qualifier
              // then skip to the beginning of the next qualifier
  
              /* ie, go from:
                  'some_id + sizeof (int)'
                   ^
  
              to here:
                  'some_id + sizeof (int)'
                             ^
              */
          }
      }
  
      if (!tks-&gt;len){
          free (tks);
          return 0;
      } else return tks;
  }
  </code></pre>
  
  <hr>
  
  <p><strong>Possible Solutions:</strong></p>
  
  <hr>
  
  <p><strong>Contextual Solutions:</strong></p>
  
  <p>I'm considering the following:</p>
  
  <ul>
  <li><p>Scan the large string once, and add a function to evaluate/adjust the tokens markers every time there is user input (instead of re-scanning the entire document over and over). I expect that this will fix the bottleneck because there is <em>much less</em> parsing involved. But, it doesn't completely fix the program, because the initial scan may still take a <em>really</em> long time.</p></li>
  <li><p>Optimize token-scanning algorithm (see below)</p></li>
  </ul>
  
  <p>I've also considered, but have rejected, these optimizations:</p>
  
  <ul>
  <li>Scanning the code that is only on the screen. Although this would fix the bottleneck, it would limit the ability to find user-defined tokens (ie variable names, function names, macros) that appear earlier on than where the screen starts.</li>
  <li>Switching the text into a linked list (a node per line), rather than a monolithic array. This doesn't really help the bottleneck. Although insertions/deletions would be quicker, the loss of indexed access slows down the parser. I think that, also, a monolithic array is more likely to be cached, than a broken-up list.</li>
  <li>Hard coding a scan-tokens function for every language. Although this could be the best optimization for performance, it's doesn't seem practical in a software development point of view.</li>
  </ul>
  
  <p><strong>Architectural solution:</strong></p>
  
  <p>With assembly language, a quicker way to parse these strings would be to load characters into registers and compare them <code>4</code> or <code>8</code> bytes at a time. There are some additional measures and precautions that would have to be taken into account, such as:</p>
  
  <ul>
  <li>Does the architecture support unaligned memory access?</li>
  <li>All strings would have to be of size <code>s</code>, where <code>s % word-size == 0</code>, to prevent reading violations</li>
  <li>Others?</li>
  </ul>
  
  <p>But these issues seem like they can be easily fixed. The only problem (other than the usual ones that come with writing in assembly language) is that it's not so much an algorithmic solution as it is a hardware solution.</p>
  
  <p><strong>Algorithmic Solution:</strong></p>
  
  <p>So far, I've considered having the program rearrange the list of keywords to make a binary search algorithm a little more possible.</p>
  
  <p>One way I've thought about rearranging them for this is by switch the dimensions of the list of keywords. Here's an example of that in <code>C</code>:</p>
  
  <pre><code>// some keywords for the C language
  
  auto  // keywords[0]
  break // keywords[1]
  case char const continue // keywords[2], keywords[3], keywords[4]
  default do double
  else enum extern
  float for
  goto
  if int
  long
  register return
  short signed sizeof static struct switch
  typedef
  union unsigned
  void volatile
  while
  
  /* keywords[i] refers to the i-th keyword in the list
   *
   */
  </code></pre>
  
  <p>Switching the dimensions of the two-dimensional array would make it look like this:</p>
  
  <pre><code>    0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 3 3 3
      1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2
    -----------------------------------------------------------------
  1 | a b c c c c d d d e e e f f g i i l r r s s s s s s t u u v v w
  2 | u r a h o o e o o l n x l o o f n o e e h i i t t w y n n o o h
  3 | t e s a n n f   u s u t o r t   t n g t o g z a r i p i s i l i
  4 | o a e r s t a   b e m e a   o     g i u r n e t u t e o i d a l
  5 |   k       i u   l     r t           s r t e o i c c d n g   t e
  6 |           n l   e     n             t n   d f c t h e   n   i
  7 |           u t                       e               f   e   l
  8 |           e                         r                   d   e
  
  // note that, now, keywords[0] refers to the string "abccccdddeeefffiilrr"
  </code></pre>
  
  <p>This makes it more efficient to use a binary search algorithm (or even a plain brute force algorithm). But it only words for the first characters in each keyword, afterwards nothing can be considered 'sorted'. This may help in small sets of words like an a programming language, but it wouldn't be enough for a larger set of words (like in the entire English language).</p>
  
  <p>Is there more than can be done to improve this algorithm?</p>
  
  <p>Is there another approach that can be taken to increase performance?</p>
  
  <p><strong>Notes:</strong></p>
  
  <p><a href="https://stackoverflow.com/questions/3550552/what-is-the-fastest-way-to-parse-text">This question</a> from SO doesn't help me. The Boyer-Moore-Horspool algorithm (as I understand it) is an algorithm for finding a sub-string within a string. Since I'm parsing for <em>multiple</em> strings I think there's much more room for optimization.</p>