Fast Parsing

I've been attempting to optimise my state machine based text parser. As a precursor to making it do Unicode and act as a base layer for a JSON parser, HTML parser etc.
The internet tells me that Google's V8 can crunch through ASCII characters at ~1/10ns if you can believe that. I can't get closer than an order of magnitude with about ~1/150ns. At least that's down from ~1/1000ns this morning.

Here's what I've done so far:

I branched my basic state machine which uses std::function for it's events.
std::function has now been replaced with qor::tef (Type Erased Function) ported from Magic Function by Leandro Gracia Gil.
That should mean each call/event has half the overhead of std::function

I removed the suspend event from the new Workflow variant, Fastflow, altogether as the parser framework doesn't use.

The replacement Fastflow steps and all their derivatives now use a custom allocator, or in QOR framework terms they have a custom memory source policy.

template<> struct source_of< data::parser::text::utf8char >{ typedef memory::FastSource type;};

FastSource is a per-thread stack style arena which only free's when pages empty out. Perfect for large numbers of small allocations which go away when the parser is finished.

I also tried the per-thread SmallObjectSource which is a little more space efficient. The performance was identical to native but that's expected as this is a single threaded scenario so there's no contention for the global heap.

I had profiled the parsing of a 73KB file using the framework's built-in profiling. Hence the base line 1 microsecond per character.
When that couldn't tell me where the time was going I used the Visual Studio profiler to dig deeper into what was happening.

I'd already played about with the buffer size used to read the underlying file and surprisingly bigger was not better. Performance peaked at ~60-120 bytes and tailed off with a larger buffer. The buffers shouldn't get reallocated in use so this is odd and I'll need to dig deeper to determine why. I expected a single buffer big enough to consume the whole file at once would be optimal. Apparently not. I set it at 64 bytes.

For now I'm excluding the IO time and focussing on the parser where an
unexpectedly a large chunk of the time was spent pushing and popping to the std::stack<> of the state machine itself. I minimised this by using std::stack::top when mutating the top node rather than popping it and then pushing it back later. That wasn't enough so I overrode the underlying container over which std::stack is an adapter.

It now uses a std::vector instead of a std::deque

std::stack< ref_of<fastflow::Step>::type, std::vector< ref_of<fastflow::Step>::type > > m_StepStack;

So I can reserve space in the vector in advance.

std::vector< ref_of<fastflow::Step>::type > stepVector;
stepVector.reserve(64);
m_StepStack = std::stack< ref_of<fastflow::Step>::type, std::vector< ref_of<fastflow::Step>::type > >(std::move(stepVector));

With a simple parse tree for repeatedly tokenizing characters this should be more than enough to avoid reallocation completely.

Now the flame graph looks like this:

As you can see the parse is taking almost the same time as the I/O. The two together are ~22.5ms on a 4GHz Zen3 CPU Core.

I've had a look at the V8 source code for clues as as to what they might be doing to be 10x more efficient but it's certainly not obvious.

My code will be up at QOR experimental as soon as I've assessed what else all those changes have broken.
Running your own memory memory allocators tends to either work smoothly or blow up pretty spectacularly.

I'd welcome any suggestions as to what else I could optimise, how to get similar performance data on Linux or if you've been down a similar road.

I hope your day was as interesting as mine.