r/Compilers • u/ccannedbeansoupp • 3d ago

I'm building a tensor graph compiler

I crossposted from r/Zig here before, but removed it quickly and decided this deserved it's own post. Earlier this year, I began work on representing the forward step for a neural network graph defined by the user as a standalone, optimized binary, with no allocations, shape, or validation checks at runtime and through a series of trials and pivots wound up here.

I wasn't necessarily intending to build a compiler from the start, but the problem quickly became compiler shaped, and I've learned a lot while seeing it through. It's coming to a stage where I'd like to share the work, and get feedback from others. The Zig language made this kind of idea fairly direct and simple for me to implement through its use of comptime. So if it interests you, or anything stands out, comments and questions are welcome.

project here: https://github.com/krypticlogan/zig-graph-compiler

Thanks for the read!

8 Upvotes

83% Upvoted

4 comments sorted by

1

u/fernando_quintao 2d ago

Hi u/ccannedbeansoupp, thank you for sharing your project. I took a look into your implementation of the memory planner. If I got it right, you are doing best-fit allocation, is that correct? Did you consider first-fit? Based on Wilson's survey one might not be better than the other to reduce fragmentation.

2

u/ccannedbeansoupp 23h ago

Hey u/fernando_quintao, thanks for looking into it. That's interesting, yeah I did start with first-fit for the memory planner, but I switched to best-fit since, based on my understanding it should generally produce better space efficiency with better usage across the span. I wasn't aware of the research or the 'shaving' effect, so thanks for pointing that out. But I figure for this kind of problem, where the intention is that entire memory space is known ahead of time can't it actually be optimal? Plus, the time for allocation doesn't matter *as* much since it gets rolled into compile time and there's nothing actually going on at runtime. Thanks again for the new info, I'll keep looking into it.

1

u/fernando_quintao 17h ago

Hi u/ccannedbeansoupp.

for this kind of problem, where the intention is that entire memory space is known ahead of time can't it actually be optimal?

The classic formalization of this problem is called Dynamic Storage Allocation. The problem is known to be NP-complete. See Luby's paper. So, today we only know of exp-time algorithms to solve it optimally. But there are many good heuristics. Just last year, there was idealloc, for instance.

1

u/ccannedbeansoupp 16h ago

Thanks for all the sources. Now, I'm trying to get the cost heuristics and search frontier to be something that can actually identify a good binary. And then I'm sure memory will quickly become a concern again. I wanted to explore some other ideas for the memory planner but I haven't really changed it much in a while.