Slice search and vectorized wildcard search for C++

By Kirk J Krauss

What’s Here

A discussion of C++ constructors and methods, of the FastUtf8::Uniseries C++ class, for searching within UTF-8 content at the scope of a virtual memory region, such as a mapped view of a file.  The constructors and methods include:

The discussion centers on the design of a means of performing wildcard-driven queries on hierarchical semistructured data.  The queries are performed by a method of the Uniseries class, named ::[case]pSelectWild().  Because not all semistructured data is hierarchical, the arrangement of methods that enable queries on hierarchical data can be rearranged to fit other forms of data, such as graphs or lists.  These methods are intended to operate on slices of relatively large content blocks, such as portions of memory-mapped views, to enable queries on datasets that might otherwise push the limits of single-node systems.

Parameterized constructors: when not to link a content buffer’s lifespan with that of an object

There’s much that can be said in favor of limiting the scope of a search for a needle in a haystack.  If software can keep track of an address range in which data of interest can be found, it can save the needless overhead of searching outside of that range.  For C++ developers, keeping track of an address range typically involves keeping track of pointers.  Tracking multiple ranges, each associated with a certain identifiable bunch of data, also involves a degree of data organization that allows for a workable scheme for tracking the ranges.

The world of semistructured data can be thought of as a world effectively working with range tracking schemes, already, because the data is often arranged hierarchically.  Within the hierarchy, specific beginning and ending locations for a range are easy for a machine to pick out.  At the same time, nothing generates semistructured data faster than a machine.  The data may accumulate from sensors, cloud applications, smart appliances, logs, message queues, or other services.

Of course, not all of that data is hierarchical.  There are several paths toward organizing semistructured data.  Most any path might begin with separating large chunks of uniserial data into slices.  Data can be sliced in may ways – such as by source, by time frame, by purpose, or by its relationship – hierarchically speaking, or otherwise – with other data.

The functionality traditionally used for ASCII text isn’t aimed toward sliced data.  Classic string functions tend to operate on a string as a whole, ending either at a terminating null or at a limit associated with the string’s full length.  Terminating nulls or whole-string lengths aren’t suitable boundaries for functionality that targets slices within the strings.  More significantly, object-oriented code applied to strings may treat an in-memory text buffer as a fundamental part of an object – a chunk of built-in instance data – and thus a block to be deallocated within the object-oriented paradigm itself.  Constructing a slice of a larger string as a separate object, with a destructor that attempts to deallocate the slice once the object goes out of scope, could have unintended and possibly disastrous results.

What’s needed is a class for handling slices of text content.  Instances of such a class may be arranged, at construction time, to deallocate memory when they’re destroyed.  Alternatively, they may be arranged to leave the deallocation task to code external to the class.  This alternative is most called for when the slice is a portion of a large file that may not be entirely memory-resident.  Suppose, for example, that the XML content in the ASCII data file for the JSON and XML demo program (in the FastUTF8 > Demos path on GitHub) had been a portion of a much larger file.  The virtual memory region corresponding to a mapped view for that portion might look something like the green swath in Fig. 1.  If we want to find some particular content within that swath, we first would like to construct a Uniseries object that refers to a portion of it.

As a first step toward enabling objects to work with slices, the parameterized constructors for a FastUtf8::Uniseries come with two flags: a bWrapBuffer flag that tells the constructor to work with the data in place rather than make a copy, and a bDeallocOnDestruct flag.  When both flags are true, or when both are false (the default case), the content buffer for the new Uniseries object will get deallocated once the object is destroyed.  Otherwise, when an existing buffer is referenced by pInbound and this flag is true, the constructor sets the new Uniseries object’s IS_DEALLOCATED_EXTERNALLY flag and leaves deallocation of the object’s content buffer to be handled by some code other than the Uniseries destructor.

Slice search: finding a slice within a larger slice

The need for handling text in slices is on the rise.  Switching from ASCII to UTF-8 entails allocating relatively large blocks.  For example, consider an ASCII string that’s expected to contain up to n characters.  If we swap out that string for UTF-8 content, say by constructing a FastUft8::Uniseries in place of a std::string, how much do we need to increase the block size to accommodate the change?  Probably the nearest UTF-8 equivalent to an ASCII character is a code point, which can occupy just a single byte – or as many as 4 bytes.  To be certain that our UTF-8 content can have as many arbitrary code points as our original ASCII string had characters, our buffer has to expand from n to (4 × n) bytes.

Developers working with a large and growing dataset may speak in terms of vertical vs. horizontal scaling – that is, beefing up the machines handling the data vs. distributing the data-handling tasks across more machines.  Another option, sometimes overlooked, is getting more from the existing machine(s).  It isn’t a far-fetched notion to consider what might be called “virtual scaling” – software that manages its dataset more effectively – before resorting to either beefing up or building out the hardware

The computer you’ve already got is remarkable.  An off-the-shelf system, especially if it’s been chosen with significant data crunching in mind, offers a pipelined superscalar architecture, speculative execution, multilevel caching, gigabytes of RAM, terabytes of storage, and perhaps built-in redundancy such as a disk array.  Some servers even have redundant fans.  If you’re hitting a data processing limit, or even if your machine just seems to be breaking a sweat, maybe it’s not the hardware that’s lacking.

The operating system is remarkable, too.  Not only has internationalized content management become normal, but so has a 64-bit virtual address space.  How can this help, when some of the beefiest machines can’t map more than a small fraction of those virtual addresses to physical addresses?  If software overcommits memory by loading a large dataset that approaches or exceeds the hardware’s physical capacity, won’t the system thrash to a near stop?

A virtual memory region can be mapped, just in part, to a file that resides largely on disk.  True, your software can’t walk the entire region, bottom to top, without lots of paging.  As with other techniques for working with large datasets, your code may have to deal with changes made to the data by other processes.  But a mapped view gives your code a handy way to address a file as a whole.  To map a view of large file and then work with just a slice of it, your code can provide hints to the system, indicating which portions of the file can remain on-disk.  From there, your code will need a way to find relevant content within the slice.  That’s where the FastUtf8::Uniseries methods, such as ::casepFindSlice(), can come in handy.

The Uniseries methods can be used for case-sensitive or case-insensitive search.  If you have a memory-mapped view of XML data, such as a large file containing the XML text of Fig. 1, the ::pFindSlice() or ::casepFindSlice() method can seek a particular tag to pinpoint a slice of interest.  If your search calls for more than one specific tag, and if some variety of text may be interposed between those tags, then the search may call for one of the Uniseries methods discussed next.

Wildcard search: pattern matching to find a slice within a slice

There are Uniseries methods for targeted wildcard search that are designed to search a Uniseries object as a whole.  As with the ::[case]pFindSlice() methods, those targeted wildcard search methods stop their searching when either:

For searching within a slice that’s part of a larger block of content whose length is known to extend to or beyond the slice’s end location, we don’t want to recheck for both the content’s overall length and for a last code point in the slice.  For the sake of efficiency, we’d like to leave the slice boundary recognition up to other methods, such as a pair of ::casepFind() calls for opening and closing tags, and so spare ourselves the the overhead of repeatedly counting code points and checking the count throughout the search.  Since slice search within large content, such as memory-mapped views, is pointer-driven, the methods discussed here stop their searching when either:

Otherwise, the ::pFindWildSlice() or ::casepFindWildSlice() methods work exactly like the Uniseries methods for targeted wildcard search that are designed to search a Uniseries object as a whole.

Because these methods don’t check a slice’s ending location against the content length of the associated Uniseries instance, you can code an up-front length check, or your code can get that ending location from a method that has that check built in.  No further check is needed, if the slice has been set up by a length-checking method.  It’s worth noting that Uniseries objects, like most text handling constructs, may call for thread safety measures that can protect their data from race conditions in multi-threaded scenarios.  A memory-mapped view also may call for handling scenarios where multiple processes can access the file underlying the view.  If there’s a chance that any aspect of content management – including but not limited to the result of a length check – has become stale, that’s when further checking makes sense.

Vectorized wildcard search: tracking the matches

Suppose you’ve got a set of ‘*’ wildcards in mind for a targeted wildcard search, and you’d like a way to access the chunks of content that match a certain few of those wildcards.  You might like to access your matches of choice by looking them up in a vector or array.  The zeroth match on a ‘*’ wildcard, within that match vector, would comprise the beginning and ending locations of the text corresponding to the leftmost of those wildcards within your search pattern.  The next match in the vector would correspond to the next ‘*’ wildcard in the pattern.  And so on.

The FastUTF8 namespace includes just such a MatchVector structure.  It’s based on std::array, rather than std::vector, so it can reside on the stack.  Your code can create a MatchVector to be populated via a type of multi-targeted search known as vectorized wildcard search.  Your code arranges the search by invoking the ::pVectorizeWild() or ::casepVectorizeWild() method.  Each entry in the MatchVector is a WildTarget structure.  All of the declarations we’re discussing appear in the FastUtf8 namespace scope in the FastUtf8.h file.

Listing One

namespace FastUtf8
{

  // ... 

   // Number of matches on '*' wildcards that may be stored in a std::array 
   // returned via Wild[Case]Vectorize() or Wild[Case]Select().
   constexpr std::size_t MAX_MATCHES = 0x0F;

   // Maximum code point length.
   constexpr std::size_t MAX_CODEPOINT = 0x04; 

   // The WildTarget structure represents an individual '*' wildcard match 
   // within vectorized wildcard search results.
   struct WildTarget {
       uint8_t *pBegin;   // Pointer to first code point in a match on a '*'
       uint8_t *pEnd;     // Pointer to the code point immediately after the match
   };

   // A MatchVector object contains matches corresponding to a single search 
   // on a pattern containing '*' wildcards.
   struct MatchVector {
      std::array<WildTarget, MAX_MATCHES> matches;
      std::size_t vectorSize;
   };

  // ...

The term “vectorize” is often associated with resolution-independent graphics, SIMD (Single Instruction, Multiple Data) operations, or linear algebra.  Given those other uses, is it valid to also apply the term when speaking of fetching content from separate locations in the address space and representing it in a single vector?  Putting that question to an online search engine suggests that term is reasonable for that purpose, too.

Once we’ve traversed the XML hierarchy of the previous figures down to the level where we find <entry> and </entry> tags, we can call ::casepVectorizeWild() to extract information within an entry.  By invoking the method from a loop, we can walk all the entries in a slice found via the ::casepFindSlice() and/or ::casepFindWildSlice() methods.  Given the search pattern of Fig. 5, when the method populates a MatchVector, our code can check its elements 0 and 2 to retrieve a surname and a birthdate.  The method also can (optionally) return the location where the match on the overall pattern has ended.  Our loop can continue looking for further entries from there, stopping when it reaches the end of the slice.

This discussion has centered on individual methods for slice search and for vectorized wildcard search.  The methods are implemented to enable the wild select concept for querying hierarchical semistructured content.  If your data is organized hierarchically, such as in JSON or XML format, that concept combines the methods we’ve been discussing, in a way that fits formats such as those.  The reason to invoke the methods separately may involve other data organizations, such as lists or graphs, that may reside in a virtual memory region such as a mapped view.

The design of ::[case]pSelectWild()

Most of the FastUtf8::Uniseries methods rely on C-style functions to get results to return.  This arrangement allows for most included UTF-8 functionality to be compatible with legacy C code, which can call those underlying functions directly.  But the ::casepVectorizeWild() method just discussed works with the C++ std::array container.  The method discussed next, casepSelectWild(), additionally works with std::set.  Since more than one of these methods for working with content slices aren’t legacy-C-compatible, all of the methods discussed here target C++ only.

Nevertheless, the code for the ::casepFindSlice(), ::casepFindWildSlice(), and ::casepVectorizeWild() methods is very similar to the legacy-C-compatible code for other Uniseries functionality including whole-content search and targeted wildcard search.  Your code can call the underlying C++ functions directly, like the ::casepSelectWild() method does, in case you don’t want to rely on a Uniseries instance.

There’s no salient difference between the case-insensitive Uniseries methods discussed here and the functions they invoke: the methods are essentially just wrappers for the functions.  But a Uniseries instance has an IS_CASE_INSENSITIVE flag.  There are counterparts to the methods outlined in Fig. 6, including ::pFindSlice(), ::pFindWildSlice(), ::pVectorizeWild(), and ::pSelectWild() methods.  Those methods check the IS_CASE_INSENSITIVE flag to determine whether to invoke the case-insensitive functions toward the right-hand side of Fig. 6 or their case-sensitive counterparts.

The functions called by all of these methods are declared in fastutf8.h.  The WildCaseVectorize() and WildCaseSelect() functions reside in the FastUtf8 namespace along with the Uniseries methods.  Like those methods, the functions rely on C++ conventions.

Listing Two

  // Given a pointer to UTF-8 content and pointers to the beginnng and end of 
  // a prospectively matching portion of content -- i.e., what may be a 
  // substring -- returns a pointer to any first matching sequence within the 
  // larger content, after case folding.   Returns nullptr if no match is 
  // found.
  //
  uint8_t * CaseFindSliceUtf8(
        const uint8_t *pContent,       // Haystack
        const uint8_t *pPatternBegin,  // Beginning of needle
        const uint8_t *pPatternEnd,    // End of needle
        uint8_t       **ppEnd);        // Updated loc after end of match

...

  // Targeted wildcard search for slice of pattern (case-insensitive).
  // See comments for WildFindSliceUtf8().  The wildcarded content comparison 
  // is performed with case folding, for a case-insensitive match.
  //
  uint8_t * WildCaseFindSliceUtf8(
        uint8_t       **ppBegin,       // Updated location of content to search
        const uint8_t *pPatternBegin,  // Specifier that may include wildcards
        const uint8_t *pPatternEnd,    // End of specifier
        uint8_t       **ppEnd,         // Updated location after end of match
        uint8_t       **ppTarget);     // Returned location after last '*'

...

   // Vectorized wildcard search (case-insensitive).
   // See comments for WildVectorize().  Content comparison is performed with 
   // case folding.
   //
   uint8_t * FastUtf8::WildCaseVectorize(
     uint8_t       **ppBegin,        // Updated location of content to search
     uint8_t       **ppEnd,          // Updated location where search ends
     const uint8_t *pPatternBegin,   // Specifier that includes wildcards
     const uint8_t *pPatternEnd,     // End of specifier
     MatchVector&  pTargets);        // Populated matches

...

   // Hierarchical content selection (case-insensitive).
   //
   uint8_t * FastUtf8::WildCaseSelect(
     const uint8_t *pBegin,        // Location of content to search
     uint8_t       **ppEnd,        // Updated ending location of search
     const uint8_t *pFullPattern,  // Specifier that includes wildcards
     int           iLevel,         // Count of nested outer '*' wildcards
     ResultSet *pResultSet);       // Set of vectors of matches for each '*'

The ::casepSelectWild() method invokes WildCaseSelect(), which invokes the first three functions in the order they appear above, as it walks the search pattern (the slice between pPatternBegin and pPatternEnd) from the outside in.

The WildCaseSelect() function operates as follows:

For each of these case-insensitive functions and methods, there’s a corresponding case-sensitive method whose name doesn’t include “case” or “Case.”  Invoke those routines, instead of the routines named above, whenever you’d like a case-sensitive match, MatchVector, or ResultSet.  The operations of all of these functions and methods are just the same as with their case-insensitive counterparts, except that they’re case-sensitive.

To switch off the optional check for a match on all tails in WildSelect() and WildCaseSelect(), you can unset the g_bMatchAllTails flag, defined in fastutf8.h.  By default, these functions seek a complete match on the inbound search pattern.  When the flag is false, they stop seeking a match after the last ‘*’ wildcard in the pattern and return any result of vectorized wildcard search on the portion of the pattern corresponding to the nesting level specified by the iLevel value – even if the portion of the overall pattern after the last wildcard hasn’t been matched.  Setting the flag to false may be useful for finding matches within incomplete or streaming data sets.

Knowing how the wild select concept has been implemented can be useful in case you’re contemplating data organized in some arrangement other than a typical JSON or XML hierarchy.  For a guide to using the implementation itself, refer to the introduction to querying semistructured UTF-8 content.  To see it in action, build the JsonAndXmlDemo.cpp code in the Demos path at GitHub > kirkjkrauss > FastUtf8.

Correctness and performance tests

The test set that covers basic targeted wildcard search is extended, with fairly simple modifications, to cover the Wild[Case]FindSliceUtf8() and Wild[Case]Vectorize() routines.  The code for the tests is included in the testutf8.cpp file that’s part of the FastUtf8 file set on GitHub.

The tests of the screenshot below ran with 500K repetitions.  We can see that the performance of Wild[Case]FindSliceUtf8() and Wild[Case]Vectorize() is slightly reduced compared to that of basic targeted wildcard search.  That’s because the basic search knows it’s handling ASCII text and saves itself the overhead of traversing it via UTF-8-aware logic.  The functions for vectorized wildcard search, and for slice search generally, don’t include ASCII-specific versions.

Nevertheless, tests show that the performance of basic targeted wildcard search, over bibliographical data in ASCII, is several times faster than that of Google-generated code for the same search based on std::string.  This means that code based on FastUtf8’s methods for vectorized wildcard search and slice search are likely to outperform std::string-based code intended for a particular lookup in JSON or XML data.

The discussion above hasn’t delved into the mechanics of managing a large data file.  There can be paging overhead getting a usable portion of the content into a virtual memory region and/or locating a particular tag or other landmark within the content.  There can be a need for handling either multithreaded acess to the file or updates made to the file by other processes, or both.  There also can be platform-specific considerations.  Then again, plenty of documentation covers safe file handling and virtual memory practices.  The discussion here has taken over where that documentation tends to leave off, covering methods for working with slices within the larger content.  A solution involving semistructured data in quantity is best built with a complete picture in mind.

The screenshot in Fig. 4 is taken from DuckDuckGo® and belongs to Duck Duck Go, Inc.

The FastUtf8 source code is available at GitHub > kirkjkrauss > FastUtf8.  The above source code listings are extracted from that code, including code from the FastUtf8.cpp file and from files in the Demos path.  The listings are formatted using the SyntaxHighlighter library, copyright (c) 2004-2013, Alex Gorbatchev.  The screenshot from DuckDuckGo was taken in response to series of queries related to uses of the term “vectorization” on October 16, 2026.

All other materials copyright © 2026 developforperformance.com.

C++ and its logo are trademarks of the Standard C++ Foundation.  Windows® and Visual Studio® are trademarks or registered trademarks of Microsoft Corp.  Unix® is a registered trademark of The Open Group.  Linux® is a registered trademark of Linus Torvalds.  Ubuntu® is a registered trademark of Canonical Ltd.  DuckDuckGo® is a registered trademark of Duck Duck Go, Inc.

Develop for Performance