www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - (SIMD) Optimized multi-byte chunk scanning

reply =?UTF-8?B?Tm9yZGzDtnc=?= <per.nordlow gmail.com> writes:
I recall seeing some C/C++/D code that optimizes the comment- and 
whitespace-skipping parts (tokens) of lexers by operating on 2, 4 
or 8-byte chunks instead of single-byte chunks. This in the case 
when token-terminators are expressed as sets of (alternative) 
ASCII-characters.

For instance, when searching for the end of a line comment, I 
would like to speed up the while-loop in

     size_t offset;
     string input = "// \n"; // a line-comment string
     import std.algorithm : among;
     // until end-of-line or file terminator
     while (!input[offset].among!('\0', '\n', '\r')
     {
         ++offset;
     }

by taking `offset`-steps larger than one.

Note that my file reading function that creates the real `input`, 
appends a '\0' at the end to enable sentinel-based search as 
shown in the call to `among` above.

I further recall that there are x86_64 intrinsics that can be 
used here for further speedups.

Refs, anyone?
Aug 23
parent reply Igor <stojkovic.igor gmail.com> writes:
On Wednesday, 23 August 2017 at 22:07:30 UTC, Nordlöw wrote:
 I recall seeing some C/C++/D code that optimizes the comment- 
 and whitespace-skipping parts (tokens) of lexers by operating 
 on 2, 4 or 8-byte chunks instead of single-byte chunks. This in 
 the case when token-terminators are expressed as sets of 
 (alternative) ASCII-characters.

 For instance, when searching for the end of a line comment, I 
 would like to speed up the while-loop in

     size_t offset;
     string input = "// \n"; // a line-comment string
     import std.algorithm : among;
     // until end-of-line or file terminator
     while (!input[offset].among!('\0', '\n', '\r')
     {
         ++offset;
     }

 by taking `offset`-steps larger than one.

 Note that my file reading function that creates the real 
 `input`, appends a '\0' at the end to enable sentinel-based 
 search as shown in the call to `among` above.

 I further recall that there are x86_64 intrinsics that can be 
 used here for further speedups.

 Refs, anyone?
On line comments it doesn't sound like it will pay off since you would have to do extra work to make sure you work on 16 byte aligned memory. For multi-line comments maybe. As for a nice reference of intel intrinsics: https://software.intel.com/sites/landingpage/IntrinsicsGuide/
Aug 25
parent reply =?UTF-8?B?Tm9yZGzDtnc=?= <per.nordlow gmail.com> writes:
On Friday, 25 August 2017 at 09:40:28 UTC, Igor wrote:
 As for a nice reference of intel intrinsics: 
 https://software.intel.com/sites/landingpage/IntrinsicsGuide/
Wow, what a fabulous UX!
Aug 25
parent Cecil Ward <d cecilward.com> writes:
On Friday, 25 August 2017 at 18:52:57 UTC, Nordlöw wrote:
 On Friday, 25 August 2017 at 09:40:28 UTC, Igor wrote:
 As for a nice reference of intel intrinsics: 
 https://software.intel.com/sites/landingpage/IntrinsicsGuide/
Wow, what a fabulous UX!
The pcmpestri instruction is probably what you are looking for? There is a useful resource in the Intel optimisation guide. There is also an Intel article about speeding up XML parsing with this instruction, but if memory serves it's really messy - a right palaver. A lot depends on how much control, if any you have over the input data, typically none I quite understand. Based on this article, https://graphics.stanford.edu/~seander/bithacks.html I wrote a short d routine to help me learn the language as I was thinking about faster strlen using larger-sized gulps. The above article has a good test for whether or not a wide word contains a particular byte value somewhere in it. I wrote a bool hasZeroByte( in uint64_t x ) function based on that method. I'm intending to write a friendlier d convenience routine to give access to inline pcmpestri code generation in GDC when I get round to it (one instruction all fully inlined and flexibly optimised at compile-time, with no subroutine call to an instruction). Agner Fog's libraries and articles are superb, take a look. He must have published code to deal with these C standard library byte string processing functions efficiently with wide aligned machine words, unless I'm getting very forgetful. A bit of googling?
Aug 26