High-performance multi-literal matching algorithm
Methods, software, and apparatus for implementing a high-performance multi-literal matching algorithm. Under aspects of a method, multi-literal matching is used during front-end processing to identify match candidates based on suffix patterns. An extended SHIFT-OR algorithm is performed using the chunk of data as an input to identify match candidates for the suffix patterns, wherein the extended SHIFT-OR algorithm shifts match indicia in the plurality of rows across predetermined bit boundaries and aligns the match indicia corresponding to target suffixes into single columns. Match candidates are indicated when OR'ed column values yield a ‘0’. Match verification for one or more search strings containing the suffix patterns is then performed by a back-end. The scheme eliminates false positives at the predetermined bit boundaries, providing substantial improvement in front-end accuracy and performance.
1. A method for performing multi-literal matching, comprising:
sampling a chunk of data from a byte stream for a document or for a stored document, the chunk of data comprising a character string comprising n bytes;
identifying a plurality of target suffixes corresponding to respective substring patterns in one or more search strings for which string matching is to be performed;
performing an extended SHIFT-OR algorithm using the chunk of data as an input to identify match candidates for the plurality of target suffixes, wherein the extended SHIFT-OR algorithm shifts match indicia in a plurality of rows of a SHIFT-OR mask table across predetermined bit boundaries and aligns the match indicia corresponding to target suffixes into single columns, the extended SHIFT-OR algorithm outputting zero or more match candidates; and
performing, based on the zero or more match candidates, match verification for the one or more search strings.
2. The method of claim 1 , wherein n comprises 64 bytes, and the method is performed by executing a plurality of 512-bit Single Input Multiple Data (SIMD) instructions on a processor.
3. The method of claim 2 , wherein one of the plurality of 512-bit SIMD instructions comprises a VPERMB (Permute Packed Bytes Elements) instruction that performs a bit level shuffle in a 64-byte source according to a 64-byte control vector.
4. The method of claim 3 , further comprising:
for a suffix having a length of m characters, configuring the control vector to shift rows associated with the suffix by m-l cells to the right.
5. The method of claim 1 , wherein the SHIFT-OR mask table employs character masks at a byte level.
6. The method of claim 1 , wherein the SHIFT-OR mask table employs character masks at a nibble level.
7. The method of claim 1 , wherein at least a portion of the plurality of target suffixes are grouped in buckets of 8 , and wherein cells for rows in the SHIFT-OR mask table associated with a given bucket of 8 suffixes contains match indicia associated with characters in the bucket of 8 suffixes at a byte level or nibble level.
8. The method of claim 1 , wherein the extended SHIFT-OR algorithm performs a shift operation corresponding to an overlapped load, wherein k bytes of a previous chunk of data are combined with n-k bytes of a current chunk of data.
9. The method of claim 1 , wherein n=64 and wherein the method eliminates false positives at byte offsets of 0, 16, 32, and 48 bytes.
10. The method of claim 1 , wherein the method operations are repeated for a plurality of chunks of data to identify search string matches for a document.
11. A non-transitory tangible machine-readable medium having instructions stored thereon comprising a software program or module for performing multi-literal matching of a byte stream for a document or for a stored document, wherein execution of the instructions on a processor of a computing system enables the computing system to:
sample a chunk of data from a byte stream for a document or from a stored document, the chunk of data comprising a character string comprising n bytes;
read a plurality of target suffixes corresponding to respective substring patterns in one or more search strings for which string matching is to be performed;
perform an extended SHIFT-OR algorithm using the chunk of data as an input to identify match candidates for the plurality of target suffixes, wherein the extended SHIFT-OR algorithm shifts match indicia in a plurality of rows of a SHIFT-OR mask table across predetermined bit boundaries and aligns the match indicia corresponding to target suffixes into single columns, the extended SHIFT-OR algorithm outputting zero or more match candidates; and
perform, based on the zero or more match candidates, match verification for the one or more search strings.
12. The non-transitory tangible machine-readable medium of claim 11 , wherein n comprises 64 bytes, and wherein the instructions include one or more 512-bit Single Input Multiple Data (SIMD) instructions.
13. The non-transitory tangible machine-readable medium of claim 12 , wherein the one or more 512-bit SIMD instructions comprises a VPERMB (Permute Packed Bytes Elements) instruction that performs a byte level shuffle in a 64-byte source according to a 64-byte control vector.
14. The non-transitory tangible machine-readable medium of claim 11 , wherein the extended SHIFT-OR algorithm performs a shift operation corresponding to an overlapped load, wherein k bytes of a previous chunk of data are combined with n-k bytes of a current chunk of data.
15. The non-transitory tangible machine-readable medium of claim 11 , wherein n=64 and the extended SHIFT-OR algorithm eliminates false positives at byte offsets of 0, 16, 32, and 48 bytes.
16. A computing system, comprising:
a processor, coupled to memory, having a plurality of cores on which instructions are executed; and
instructions comprising a software program or module for performing multi-literal matching of a byte stream for a document or for a stored document, wherein execution of the instructions on a processor of a computing system enables the computing system to:
sample a chunk of data from a byte stream for a document or from a stored document, the chunk of data comprising a character string comprising n bytes;
read a plurality of target suffixes corresponding to respective substring patterns in one or more search strings for which string matching is to be performed;
perform an extended SHIFT-OR algorithm using the chunk of data as an input to identify match candidates for the plurality of target suffixes, wherein the extended SHIFT-OR algorithm shifts match indicia in a plurality of rows of a SHIFT-OR mask table across predetermined bit boundaries and aligns the match indicia corresponding to target suffixes into single columns, the extended SHIFT-OR algorithm outputting zero or more match candidates; and
perform, based on the zero or more match candidates, match verification for the one or more search strings.
17. The computing system of claim 16 , wherein n comprises 64 bytes, and wherein the instructions include one or more 512-bit Single Input Multiple Data (SIMD) instructions.
18. The computing system of claim 17 , wherein the one or more 512-bit SIMD instructions comprises a VPERMB (Permute Packed Bytes Elements) instruction that performs a byte level shuffle in a 64-byte source according to a 64-byte control vector.
19. The computing system of claim 16 , wherein the extended SHIFT-OR algorithm performs a shift operation corresponding to an overlapped load, wherein k bytes of a previous chunk of data are combined with n-k bytes of a current chunk of data.
20. The computing system of claim 16 , wherein n=64 and the extended SHIFT-OR algorithm eliminates false positives at byte offsets of 0, 16, 32, and 48 bytes.