[Proposal] Native C++ FST Writer implementation (2x Speedup) - Interest in Adoption?

[johnjohnlin]

Hi Tony and maintainers,

I have been working on optimizing the FST writer performance for Verilator.

The Optimization: I implemented a native C++ rewrite of the FST writer. The key architectural change is moving from string-based intermediate storage to native integer (uintX_t) storage. This eliminates the overhead of integer-to-string conversions during simulation, resulting in a 2x speedup in dumping time for Verilator simulations (tested on a RISC-V core).

Compatibility:

• The implementation is API-compatible.
• It provides a native C++ class for performance.
• It includes an extern "C" wrapper, making it a drop-in replacement for the existing C API.

The Question: I am coordinating with Wilson Snyder regarding integrating this into Verilator. He suggested I reach out to ask if gtkwave would be interested in adopting this C++ implementation upstream (Link)?

We are open to licensing this under MIT to match libfst.

If you are interested, I can prepare a PR or a standalone repository for review. If gtkwave prefers to stay strictly C-only, we will proceed with maintaining this as a separate library for Verilator.

[tbybell]

I need to look at it in detail, but an initial (not comprehensive) read over the code shows what I see so far to be an interesting and compact implementation. Note that I'm not 100% anti-C++ code as gtkwave already uses wrappers to interface the FsdbReader code, so I won't consider what you did to be any kind of non-negotiable deal breaker. My main complaints about C++ code mostly involve abuse of templates such that error messages from the compiler are 20 lines long and incomprehensible, or usage of C++year_now features that break LTS versions of OSs such as the RHELs that don't pick up the very newest version of a C++ compiler. Moreover, I don't like C++ code I can't read because I haven't been keeping up on trendy new C++isms. :-)

Note that if you're going to benchmark, you should use much larger models than the ones that generate the golden_bench data that I see in the git repo. Ideally, I'd want ("you can't always have what you want...") to see something >1M signals (real model, not multiple instantiations of the same blocks) because then there is measurable deduplication overhead, rampant TLB thrashing, L3 misses, etc. during context flush as well as during signal value change emission as the writer is constantly dueling with the simulator. On larger models, the equivalent of context flush in your implementation is more than likely going to eat into your perf gains. You certainly will measure gains, but I don't know how much. Wilson probably can point you to where some decently-sized models exist.

All of the above said, it looks good so far and I'm quite impressed. OK, there are some missing features and I "get" that. The main thing that sets my teeth on edge right now is the existing FST code has a lot of years of testing in the field behind it. I'm open to other writer or reader implementations such as yours, but your code at the moment needs more testing, and definitely against industrial sized designs if possible.

This is me thinking out loud, but note that there was recent chatter in the past six months about "It's time for an FST2", so what you are proposing might be better suited as its conceptual base implementation with Verilator being good for proof of functional soundness of writer internals. I don't know, but it's something to keep in mind. The main thing right now is gtkwave can read what you write which is awesome, so immediate incorporation under the gtkwave/libfst umbrella isn't a pressing matter.

If it's not painful, sure, generate a PR against libfst, then Ralf and I can see what this would look like, if it makes sense, etc. There is no hurry on that as I'm going to get thrust back into the work world in a couple of days and I'm already busy leading up to that.

CPU: AMD Ryzen 9 7950X, release mode, cell is the runtime (ms).

Always glad to see that: Boston team made a great chip with that one.

[johnjohnlin]

Hi Tony,

You were right. I benchmarked the first 300k cycles on NVDLA:gnet (0.53M signals), and the speedup dropped to 1.0x (parity).

Profiling & Lessons Learned:

1. The "Virtual" Cost: I initially attempted to use virtual classes to optimize memory for different bit-widths. This actually caused a regression to 0.8x due to vtable lookups and branch prediction misses. I stripped all virtual dispatch out just to restore parity.
2. The Real Bottleneck: The remaining issue appears to be severe cache thrashing and memory bandwidth saturation.
   • Rough Calculation: Merely scanning the signal handles every cycle is expensive: 0.53M signals * 32B/handle * 300k cycles / 60GB/s ≈ 80s theoretical limit if fully accessed.
   • Observation: While the actual overhead is lower (~10-15s) due to activity factors, this aligns with the hypothesis that we are hitting the memory wall. __builtin_prefetch did not help in my experiments.

Question:
Do you have any recommendations for this memory bottleneck? Would moving to a blocked/chunked layout (to improve spatial locality) be the right direction, or is this effectively an inherent cost of tracking this many signals?

Best,
Yu-Sheng Lin

[tbybell]

Sorry to hear that. These large datasets beat on system architecture hard.

I don't have your code handy to see if you preserved usage of mmap(). To cut down on the L1TLB/L2TLB/UTLB miss penalty which could be, what, a 10-15% "tax" on the cost of loads, I'm thinking the flag MAP_HUGETLB might help, but I don't know by how much. L2TLBs given their size and implementation are going to have a limited number of read ports which is almost certainly less than the number of load pipes, so this could help some. It's hard to say. The good thing on AMD is your L1DTLB is fully associative for those large page sizes so large pages will increase the translation reach of the DTLB at any given instant.

As far as locality goes, for a while, Wilson has wanted parallel write (with read being able to accommodate it transparently) similar to how ZTDB works on emulators, so this really might turn out to be more of a reader issue. No matter what you do to improve locality, someone can always build a bigger model (this is what EDA tools have had to contend with since...forever), so yes, I'd say we have an inherent cost from tracking a large number of signals. It gets even worse with real-world models. Emulators don't dump every signal, but only enough to allow reconstruction via limited resimulation at viewer time.

[johnjohnlin]

Hi Tony,

I wanted to share a quick update following your advice on the memory bottleneck. With some refactoring, I benchmarked the implementation on NVDLA, Vortex, and OpenTitan, and achieved a 1.10x ~ 1.57x speedup even on these large designs. 2.53x-3.40x on mid-level design like small picorv32.

Here are the key findings:

1. mmap Experiment: I tested with mmap as you suggested. On my setup, the gains were minor, likely because the bottleneck had shifted to raw DRAM bandwidth due to the sheer volume of std::vector metadata overhead.
2. Aggressive Bit-packing (The Key Win for Memory Wall): I decided to attack the memory layout directly. I replaced the per-signal std::vector (approx. 32-byte overhead per signal) with a custom 16-byte packed structure. This change contributed the most to the optimization.
   • Observation: I noticed current fstapi.c handles seem to use ~32 bytes per signal; a similar bit-packing strategy might be applicable to your upstream code as well. (See appendix below for the structure).
3. Eliminating Branch Prediction Misses: I initially tried to select the most "memory-efficient" implementation for 1/2/4/8/8+ byte signals using virtual functions or if-else branches. However, the vtable lookups and branch prediction penalties were severe. I found that unifying the handling was faster, as the reduction in branch misses outweighed the slight memory waste.
   • Observation: The optimal selection of category depends on the signal bitwidth distribution in a design, 3 categories--1/(2/4)/(8/8+) or 1/(2/4/8)/(8+)--generally provides the best performance in these benchmarks.

I am about to propose this to Wilson Snyder for merging into Verilator. If you have a brief moment, I would appreciate a quick glance at the repo, specifically src/fstcpp/Writer.cpp and src/fstcpp/VariableInfo.h. Your "sanity check" or any final thoughts would be incredibly valuable before we finalize the integration.

Best regards,
Yu-Sheng Lin

Appendix: The Packed Structure

class VariableInfo final {
    // Word 0: 8B Data Pointer (nullptr or encoding capacity)
    uint8_t *data = nullptr;

    // Word 1: 8B Metadata (Bit-packed)
    // - 33b size
    // - 6b capacity_log2
    // - 12b last_written_bytes
    // - 12b bitwidth (unified handling for all byte sizes)
    // - 1b is_real
    uint64_t misc = 0; 
};

[tbybell]

I'll look at the bitpacking optimizations to see if they're applicable, thanks.

For the TLB, I'm glad it's not an issue on Zen 4. In the future, I guarantee it will be as these open source designs grow (as it was an issue in the past around 2010-11 when Andrew Vanvick was profiling FST for CVER), but don't worry about it now and only consider that it can/will be the next future bottleneck. When users show up with sim in range of 100 million signals, it'll require new profiling. That's outside the realm 99.9% of users, so I wouldn't be too concerned with it at the moment--especially given that parallel dumping would be a better option for those huge usage cases.

For the branch predict misses, you tradeoff what you can tradeoff. Where specifically is the code you have now for the most recent implementation? Is it the if (bitwidth <= 8)... at line 711 in fstcpp/VariableInfo.h? If so, that's exactly what I would do there: that's classic "devirtualization" of an indirect branch. I didn't look at your implementation in detail enough to see if you could calculate both <=8 and <=64 blindly, then steer/mux the <=8 case appropriately getting it where it needs to be inside an oversized store, which would get you down to a single branch (with most cases encountered in sim definitely being <=64b). Condition code checks as used as inputs for arithmetic ops (e.g., CMOV) don't cause a pipe flush but should be resolved in the scheduler as a missing ready. Again, I don't know if you can do that with your code.

Looks great. Fantastic work!
-Tony

[johnjohnlin]

Hi Tony,
Thanks for your reply. I am finalizing the integration of the new C++ FST writer into Verilator.

Wilson Snyder suggested that the gtkwave organization would be the ideal home for this new library (libfstpp) for long-term maintenance.

Are you open to hosting it? If not, we will proceed with hosting it under the verilator organization instead.

Best, Yu-Sheng Lin

[tbybell]

Sure, the gtkwave org would be the best place to host the writer so we avoid having fragmentation with related code bases spread all over the place.

Ralf set up https://github.com/gtkwave/libfst a little while back. I don't know the command line incantations to move projects around github, so Ralf, could you help with or do this? Thanks. My only observation at the moment is that libfstpp is a bit of a misnomer, so it might properly be libfstwriterpp to avoid confusion. I'll leave that one for Ralf to comment and decide on. I'm fine either way, but my immediate inclination is to leave it as is because eventually there will be a reader, and because of that it's less project management churn.

-Tony

p.s.: Thanks for giving back to the community and proving that the concept of open source bazaar still works.

[rfuest]

I can set up a repo as soon as we have decided on a name. I agree with Tony that name should contain writer, except when there is a plan to also implement the reader part.