6 ms·

Compiling a neural net to C for a speedup

296 points by todsacerdoti 1y ago

memming 1y ago
pretty cool write up. the interesting bits were before what the title indicated though.
enricozb 1y ago
Differentiable Logic Gate Networks [0] are super interesting. However, I still don't like that the wiring is fixed initially rather than learned. I did some extremely rough research into doing learnable wirings [1], but couldn't get past even learning ~4-bit addition. [0]: https://arxiv.org/abs/2210.08277 https://arxiv.org/abs/2210.08277 [1]: https://ezb.io/thoughts/program_synthesis/boolean_circuits/2025-03-23_learning_wirings.html https://ezb.io/thoughts/program_synthesis/boolean_circuits/2...
- awesomeMilou 1y ago
  To ruin it for everyone: They're also patented :) https://patents.google.com/patent/WO2023143707A1/en?inventor=Felix+Petersen&after=priority:20200101 https://patents.google.com/patent/WO2023143707A1/en?inventor...
  - Lerc 1y ago
    What's the innovation here? Using logic operators? Picking something from a range of options with SoftMax? Having a distribution to pick from? I remember reading about adaptive boolean logic networks in the 90's. I remember a paper about them using the phrase "Just say no to backpropagation". It probably goes back considerably earlier. Fuzzy logic was all the rage in the 90's too. Almost at the level of marketers sticking the label on everything the way AI is done today. Most of that was just 'may contain traces of stochasticity' but the academic field used actual defined logical operators for interpolated values from zero to one. A quick look on picking from a selection found https://psycnet.apa.org/record/1960-03588-000 https://psycnet.apa.org/record/1960-03588-000 but these days softmax is just about ubiquitous.
    - genewitch 1y ago
      My Zojirushi rice cooker says fuzzy logic on it, it's 15 years old, so that phrase was still marketed 15 years after "inception".
    - awesomeMilou 1y ago
      > What's the innovation here? > Having a distribution to pick from? As I understand it, it's exactly this. Specifically, representing neurons in a neural network via a probability distribution of logic gates and then collapsing the distribution into the optimal logic gate for a given neuron via hyper-parameter tuning in the form of gradient descent. The author has a few more details in their thesis: https://arxiv.org/abs/2209.00616 https://arxiv.org/abs/2209.00616 Specifically it's the training approach that's patented. I'm glad to see that people are trying to improve on his method, so the patent will likely become irrelevant in the future as better methods emerge. The author also published an approach on applying their idea onto convolutional kernels in CNN's: https://arxiv.org/abs/2411.04732 https://arxiv.org/abs/2411.04732 In the paper they promise to update their difflogic library with the resulting code, but apparently they seem to have conveniently forgotten to do this. I also think their patent is too broad, but I guess it speaks for the entire ML community that we haven't seen more patents in this area. I could also imagine that, given that the approach promises some very impressive performance improvements, they're somewhat afraid that this will be used for embedded military applications.
      - sitkack 1y ago
        Liquid NN are also able to generate decision trees.
- mattdesl 1y ago
  I think the techniques in “Weight Agnostic Neural Networks” should be applicable here, too. It uses a variant of NEAT I believe. This would allow for learning the topology and wiring rather than just gates. But, in practice it is probably pretty slow, and may not be all that different than a pruned and optimized DLGN.. https://weightagnostic.github.io/ https://weightagnostic.github.io/
- mochomocha 1y ago
  Ha! I have spent the last 2 years on this idea as a pet research project and have recently found a way of learning the wiring in a scalable fashion (arbitrary number of input bits, arbitray number of output bits). Would love to chat with someone also obsessed with this idea.
  - UncleOxidant 1y ago
    Also very interested. Do you have any code on github?
  - andy12_ 1y ago
    I also I'm very interested. I had played around a lot with Differentiable Logic Networks a couple of months ago and how to make the learned wiring scale to bigger number of gates. I had a couple of ideas that seemed to worked in a smaller scale, but that had trouble converging with deeper networks.
- hansvm 1y ago
  One of the easier solutions that does the rounds periodically (in many forms above and beyond logic gates, such as symbolic regression) is just densely connecting everything and ensuring that an identity function exists. Anneal a penalty around non-identity nodes, use L1 for the penalty, and you can learn a sparse representation. There are a number of details to work through, such as making an "identity" for 2 inputs and 1 output (just don't offer those; use gates like a half adder instead of AND or XOR, adding a post-processing step removing extra wires you don't care about), or defining "densely connected" in a way that doesn't explode combinatorially (many solutions, details only matter a little), but it's the brute-force solution, and you only pay the cost during training. There are lots of other fun ways to handle that problem though. One of my favorites is to represent your circuit as "fields" rather than discrete nodes. Choose your favorite representation for R2->Rn (could be a stack of grids, could be a neural net, who cares), and you conceptually represent the problem as a plane of wire density, a plane of "AND" density, a plane of "XOR" density, etc. Hook up the boundary conditions (inputs and outputs on the left and right side of the planes) and run your favorite differentiable PDE solver, annealing the discreteness of the wires and gates during training.
- thesz 1y ago
  Careless application of Gumbel Softmax would let your model to select same input for both inputs of a gate. Also, note that selecting a wire has all same problems as selecting an operation, such as vanishing gradient, but no apparent mitigation like residual initialization. And for wire selection gradient vanishes quicker, because there are more wires (tens and hundredths) than operations (16).
AmazingTurtle 1y ago
I recently read about DLGAs on HN and instantly thought: damn thats some hot take. But I was too stupid to implement it from the paper. Glad you got it working and documented it! Thanks!
isaacimagine 1y ago
Author here. Any questions, ask away.
- djmips 1y ago
  Was this result surprising?
  - isaacimagine 1y ago
    Yes and no. I wasn't expecting to be able to reproduce the work, so I'm just content that it works. I was very surprised by how much hyperparameter finagling I had to do to get the DLGN converging; the tiny relu network I trained at the beginning, in comparison, converged with dead-simple SGD in a third of the epochs. The speedup was surprising in the sense that the bit-level parallelism fell out naturally: that 64× speedup alone was unexpected and pretty sweet. There's likely still a lot of speed left on the table. I just did the bare minimum to get the C code working: it's single-threaded, there's no vectorization, lots of register spilling, etc. Imagine the speedup you'd get running the circuit on e.g. an FPGA. But no, it was not surprising in the sense that yeah, multiplying billions of floats is going to be much slower than a handful of parallel bitwise ops. Physics is physics, doesn't matter how good your optimizer is.
    - jgord 1y ago
      what percentage of ops were passthru ? ps. superb writeup and project
      - isaacimagine 1y ago
        Thank you! Good question, Here are the NN stats, before lowering to C: total gates | 2303 | 100.0% -------------------+------+------- passthrough | 2134 | 92.7% gates w/ no effect | 1476 | 64.1% Note the rows aren't mutually exclusive.
- Twirrim 1y ago
  You've made some mistakes with the Game of Life rules. You've missed out the overpopulation rule: Any live cell with more than three live neighbours dies Nit: > I guess there’s a harsh third rule which is, “if the cell is dead, it stays dead”. That phrasing is inaccurate, if a dead cell stayed dead, the first rule wouldn't work. I'm not sure that particular sentence adds much to the flow, honestly.
randomtoast 1y ago
Given the complexity of modern compiler optimizations, integrating a small neural network into a C compiler like GCC might help generate faster executable code by guiding optimization decisions.
- nurettin 1y ago
  -O3 -march=native is pretty much all you need and the rest is marginal or circumstantial.
  - randomtoast 1y ago
    What makes you so confident that an AI-assisted compiler couldn't significantly enhance optimizations? A relevant example of a complex problem where neural networks have improved performance is found in chess engines. Today, top-level engines like Stockfish have integrated NNUE ("Efficiently Updatable Neural Network") which has significantly boosted their performance.
    - nurettin 1y ago
      What makes me confident is the fact that I've been using gcc since 2.95 (well redhat had its patched "2.96" but yeah) so I witnessed the evolution of these parameters. What makes neural networks and learning irrelevant is because there aren't a billion parameters, most parameters don't depend on each other. It is not a search problem. You have the wrong domain. This is like saying "hey let's crack that password using neural networks, stockfish is so advanced!" And people have tried auto searching parameters, the results were as I described in my response. Moreover, imagine releasing code and having cluebies complain about trying to make it go faster with -fomit-frame-pointer. The whole idea is wasteful and cringe.
  - queuebert 1y ago
    That doesn't fix suboptimal algorithm choices, but neither would a small NN in the compiler. A big NN could rewrite large sections of code without changing the logic, but why do that during translation instead of rewriting the source?
godelski 1y ago
> I tried something new for the first time, which was to keep a journal during development. DO THIS!!! I cannot stress this enough! If you work in a professional science lab, say, physics, biology, chemistry, you are expected to keep an experiment journal. It provides more help to you than the company too (knowledge dump, liability, etc). I can't tell you how many times some stupid ass seemingly benign comment saved my behind. They're worth their weight in gold. For ML experiments I use wandb and hydra[0]. Put all your configs into hydra. Be fucking pedantic. You should log your seeds, versions, the date, and I mean everything. It only takes a few extra minutes to set this up but the one time you need it it'll save you hours. Dump all that into wandb AND your model checkpoints. You will forget what that checkpoint corresponds to. Make liberal use of wandb tags and comments (through hydra you can make these cli arguments to automate even if launching from slurm scripts). Turn on wandb's code saving. Most importantly, use those notebooks wandb gives you. Don't worry if it gets messy. It's a experiment notebook, it'll get messy. You'll get better with experience and as you find your style. It sounds like a lot of work but it really isn't. You can get this all done under 20 minutes and if you write it right you can just copy paste it moving forward (i.e. yeah, make a personal library). I can PROMISE you that one mishap will far outweigh this extra work. You look like a pretentious perfectionist but really I'm a lazy piece of shit rust doesn't want to spend hours or days debugging some stupid mistake I'm too dumb or tired to catch. The extra benefit is when shit world you can spin up some (wandb) sweeps and go do some other thing that's always behind. (On topic, stop using personal wandb accounts for your work experiments. They're like the best company out there, get your boss to pay. They provide an amazing service and are a delight to work with. I cannot speak highly enough about them. They're not the company you want to mooch from. I've literally seen this happen while working for a top 3 market cap which was already paying for seats and you just needed to send a slack message to one dude... not cool guys... not cool...) [0] https://hydra.cc/docs/intro/ https://hydra.cc/docs/intro/
- 0cf8612b2e1e 1y ago
  From my two minute skim of the docs, not encouraging that hydra only officially supports up to Python 3.11.
  - 1y ago
nine_k 1y ago
The interesting thing here is that it's not a straightforward port. JAX is already very fast, for the architecture it implements. The point is that the network is heavily contracted by removing nodes that only do pass-through, and then hugely parallelizing the computations using bitwise operations on 64 bits at once. Hence this incredible speedup.
JonChesterfield 1y ago
If you replace the uint64_t cell with an attribute((vector_size(32))) and build with march=native, the bitwise ops will work exactly as before but you'll light up the vector units on the x64 machine. Good blog post, thanks!
- isaacimagine 1y ago
  Glad you enjoyed it, and thanks for the tip!
hermitShell 1y ago
This is very fascinating as a limit case, which always serve as a good example of the bound. I think it highlights that “efficiency isn’t everything” just like in so many other systems like healthcare and justice. In this case we could figure out the activation functions by analysis, which is impossible for problems of higher dimensionality. The magic of AI isn’t in it’s efficiency, it’s in making things computable that simply aren’t by other means.
gwern 1y ago
How much of a speedup is the C compiler optimization able to achieve in terms of compiling it down to a hand-written C equivalent vs the -O0 non-optimized assembler? What does the optimized C/assembler do which isn't actually necessary and accounts for the remaining inefficiency?
- isaacimagine 1y ago
  There are 163 lines of C. Of them, with -O3, 104 lines are present in the assembly output. So the C compiler is able to eliminate an additional ~36.2% of the instructions. It doesn't do anything fancy, like autovectorization. I profiled just now: | instrs (aarch64) | time 100k (s) | conway samples (%) | | -O0 | 606 | 19.10s | 78.50% | | -O3 | 135 | 3.45 | 90.52% | The 3.45s surprises me, because it's faster than the 4.09s I measured earlier. Maybe I had a P core vs an E core. For -O0, the compiler is emitting machine code like: 0000000100002d6c ldr x8, [sp, #0x4a0] 0000000100002d70 ldr x9, [sp, #0x488] 0000000100002d74 orn x8, x8, x9 0000000100002d78 str x8, [sp, #0x470] Which is comically bad. If I try with e.g. -Og, I get the same disassembly as -O3. Even -01 gives me the same disassembly as -O3. The assembly (-0g, -01, -03) looks like a pretty direct translation of the C. Better, but also nothing crazy (e.g. no autovectorization): 0000000100003744 orr x3, x3, x10 0000000100003748 orn x1, x1, x9 000000010000374c and x1, x3, x1 0000000100003750 orr x3, x8, x17 Looking more closely, there's actually surprisingly little register spilling. I think the real question you're asking is, as I wrote: > If we assume instruction latency is 1 cycle, we should expect 2,590 fps. But we measure a number nearly 10× higher! What gives? Part of this is due to counting the instructions in the dissassembly wrong. In the blogpost I used 349 instructions, going off Godbolt, but in reality it's 135. If I redo the calculations with this new numbers, I get 2.11 instructions per bit, 0.553 million instrs per step, dividing out 3.70 gcycles/s gives 6,690 fps. Which is better than 2,590 fps, but still 3.6x slower than 24,400. But I think 3.6x is a factor you can chalk up to instruction-level parallelism,. Hope that answers your questions. Love your writing Gwern.
  - gwern 1y ago
    Thanks for checking. It sounds like the C compiler isn't doing a great job here of 'seeing through' the logic gate operations and compiling them down to something closer to optimal machine code. Maybe this is an example of how C isn't necessarily great for numerical optimization, or the C compiler is just bailing out of analysis before it can fix it all up. A fullstrength symbolic optimization framework like a SMT solver might be able to boil the logic gates down into something truly optimal, which would then be a very interesting proof of concept to certain people, but I expect that might be for you an entire project in its own right and not something you could quickly check. Still, something to keep in mind: there's an interesting neurosymbolic research direction here in training logic gates to try to extract learned 'lottery tickets' which can then be turned into hyper-optimized symbolic code achieving the same task-performance but possibly far more energy-efficient or formally-verifiably.
hy4000days 1y ago
[dead]
thirtygeo 1y ago
That approach is bananas! I had seen the source inspiration paper from Google but it's need to see it replicated and extended so shortly after.
- isaacimagine 1y ago
  +10 respect, thank you <3
gomoboo 1y ago
Relevant post from a few years ago: https://news.ycombinator.com/item?id=25290112 https://news.ycombinator.com/item?id=25290112 “ NN-512 is an open-source Go program that generates fully AVX-512 vectorized, human-readable, stand-alone C implementations of convolutional neural nets”
Vox_Leone 1y ago
Well done — really enjoyed this. We could use this kind of optimization in our library[0], which builds differentiable logic networks out of gates like AND, XOR, etc. It focuses on training circuit-like structures via gradient descent using soft logic semantics. The idea of compiling trained models down to efficient bit-parallel C is exactly the kind of post-training optimization we’ve been exploring — converting soft gates back into hard boolean logic (e.g. by thresholding or symbolic substitution), then emitting optimized code for inference (C, WASM, HDL, etc). The Game of Life kernel is a great example of where logic-based nets really shine. [0]https://github.com/VoxLeone/SpinStep/tree/main/benchmark https://github.com/VoxLeone/SpinStep/tree/main/benchmark
jjaksic 1y ago
Cool. If you do this with an LLM, someone will pay you a lot of money.
kookamamie 1y ago
> 1,744x speedup Is that 1744x or 1.7x?
- genewitch 1y ago
  Former, also there's too many digits of precision for it to be the latter.
mickey475778 1y ago
[dead]
- pjmlp 1y ago
  Or any other strongly typed natively compiled language for that matter.
Lopezkatheryn 1y ago
[dead]
andy12_ 1y ago
I also worked a long time ago in recreating the original Deep Differentiable Logic Network paper [1], so I have a couple of additions to make. > I wanted to see if I could learn the wires in addition to the gates. I still think it’s possible, but it’s something I had to abandon to get the model to converge. Actually, I read some other paper where they also learned the wiring, but they did so by alternating the training of the gates and the wires (in some iterations they learned the wiring while keeping the gates frozen, and in other they learned the gates while keeping the wiring frozen). The problem with this approach is that it is inherently non-escalable: you need a lot of gates to approximate the behavior of a simple MLP, and if you need a full NxM learned matrix to encode the wiring, the memory needed to learn, for example, MNIST, gets huge, quickly. I think that for this there are 2 fixes: - You actually don't need to learn a full NxM matrix to increase the expressivity of the network. You can, for each output gate, select a random subset of possible input gates of size K, and then you only need a learned matrix of size KxM. I did the numbers, and even a moderately small K, like 16 or 32, wildly increases the number of circuits you can learn with a smaller number of layers and gates. - You could use a LoRA kind of matrix. Instead of a matrix NxM, use a pair of matrices NxK and KxM, where K<<N,M. Learning the wiring also has other benefits. As the output gate can learn to swap the inputs if needed, you can remove some learnable gates that are "mirrors" or "permutations" of each other (a and not b, not a and b; a or not b, not a or b), which can help scale the networks to use gates of more inputs (I tried with 3-input gates and 4-input gates). Also, as the author pointed out, it was very difficult to get the models to converge. It was very frustrating that I never managed to get a working model that performed really well on MNIST. In the end, I gave up on that and I worked on how to make the network consistently learn simple 3-input or 4-input functions with perfect accuracy, and I managed to make it learn them consistently with a couple dozen iterations, which was nice. [1] https://arxiv.org/abs/2210.08277 https://arxiv.org/abs/2210.08277
- isaacimagine 1y ago
  Very cool, thank you for sharing!

296 points by todsacerdoti 1y ago

pretty cool write up. the interesting bits were before what the title indicated though.

Differentiable Logic Gate Networks [0] are super interesting. However, I still don't like that the wiring is fixed initially rather than learned. I did some extremely rough research into doing learnable wirings [1], but couldn't get past even learning ~4-bit addition. [0]: https://arxiv.org/abs/2210.08277 https://arxiv.org/abs/2210.08277 [1]: https://ezb.io/thoughts/program_synthesis/boolean_circuits/2025-03-23_learning_wirings.html https://ezb.io/thoughts/program_synthesis/boolean_circuits/2...

awesomeMilou 1y ago
To ruin it for everyone: They're also patented :) https://patents.google.com/patent/WO2023143707A1/en?inventor=Felix+Petersen&after=priority:20200101 https://patents.google.com/patent/WO2023143707A1/en?inventor...
- Lerc 1y ago
  What's the innovation here? Using logic operators? Picking something from a range of options with SoftMax? Having a distribution to pick from? I remember reading about adaptive boolean logic networks in the 90's. I remember a paper about them using the phrase "Just say no to backpropagation". It probably goes back considerably earlier. Fuzzy logic was all the rage in the 90's too. Almost at the level of marketers sticking the label on everything the way AI is done today. Most of that was just 'may contain traces of stochasticity' but the academic field used actual defined logical operators for interpolated values from zero to one. A quick look on picking from a selection found https://psycnet.apa.org/record/1960-03588-000 https://psycnet.apa.org/record/1960-03588-000 but these days softmax is just about ubiquitous.
  - genewitch 1y ago
    My Zojirushi rice cooker says fuzzy logic on it, it's 15 years old, so that phrase was still marketed 15 years after "inception".
  - awesomeMilou 1y ago
    > What's the innovation here? > Having a distribution to pick from? As I understand it, it's exactly this. Specifically, representing neurons in a neural network via a probability distribution of logic gates and then collapsing the distribution into the optimal logic gate for a given neuron via hyper-parameter tuning in the form of gradient descent. The author has a few more details in their thesis: https://arxiv.org/abs/2209.00616 https://arxiv.org/abs/2209.00616 Specifically it's the training approach that's patented. I'm glad to see that people are trying to improve on his method, so the patent will likely become irrelevant in the future as better methods emerge. The author also published an approach on applying their idea onto convolutional kernels in CNN's: https://arxiv.org/abs/2411.04732 https://arxiv.org/abs/2411.04732 In the paper they promise to update their difflogic library with the resulting code, but apparently they seem to have conveniently forgotten to do this. I also think their patent is too broad, but I guess it speaks for the entire ML community that we haven't seen more patents in this area. I could also imagine that, given that the approach promises some very impressive performance improvements, they're somewhat afraid that this will be used for embedded military applications.
    - sitkack 1y ago
      Liquid NN are also able to generate decision trees.
mattdesl 1y ago
I think the techniques in “Weight Agnostic Neural Networks” should be applicable here, too. It uses a variant of NEAT I believe. This would allow for learning the topology and wiring rather than just gates. But, in practice it is probably pretty slow, and may not be all that different than a pruned and optimized DLGN.. https://weightagnostic.github.io/ https://weightagnostic.github.io/
mochomocha 1y ago
Ha! I have spent the last 2 years on this idea as a pet research project and have recently found a way of learning the wiring in a scalable fashion (arbitrary number of input bits, arbitray number of output bits). Would love to chat with someone also obsessed with this idea.
- UncleOxidant 1y ago
  Also very interested. Do you have any code on github?
- andy12_ 1y ago
  I also I'm very interested. I had played around a lot with Differentiable Logic Networks a couple of months ago and how to make the learned wiring scale to bigger number of gates. I had a couple of ideas that seemed to worked in a smaller scale, but that had trouble converging with deeper networks.
hansvm 1y ago
One of the easier solutions that does the rounds periodically (in many forms above and beyond logic gates, such as symbolic regression) is just densely connecting everything and ensuring that an identity function exists. Anneal a penalty around non-identity nodes, use L1 for the penalty, and you can learn a sparse representation. There are a number of details to work through, such as making an "identity" for 2 inputs and 1 output (just don't offer those; use gates like a half adder instead of AND or XOR, adding a post-processing step removing extra wires you don't care about), or defining "densely connected" in a way that doesn't explode combinatorially (many solutions, details only matter a little), but it's the brute-force solution, and you only pay the cost during training. There are lots of other fun ways to handle that problem though. One of my favorites is to represent your circuit as "fields" rather than discrete nodes. Choose your favorite representation for R2->Rn (could be a stack of grids, could be a neural net, who cares), and you conceptually represent the problem as a plane of wire density, a plane of "AND" density, a plane of "XOR" density, etc. Hook up the boundary conditions (inputs and outputs on the left and right side of the planes) and run your favorite differentiable PDE solver, annealing the discreteness of the wires and gates during training.
thesz 1y ago
Careless application of Gumbel Softmax would let your model to select same input for both inputs of a gate. Also, note that selecting a wire has all same problems as selecting an operation, such as vanishing gradient, but no apparent mitigation like residual initialization. And for wire selection gradient vanishes quicker, because there are more wires (tens and hundredths) than operations (16).

AmazingTurtle 1y ago

I recently read about DLGAs on HN and instantly thought: damn thats some hot take. But I was too stupid to implement it from the paper. Glad you got it working and documented it! Thanks!

isaacimagine 1y ago

Author here. Any questions, ask away.

djmips 1y ago
Was this result surprising?
- isaacimagine 1y ago
  Yes and no. I wasn't expecting to be able to reproduce the work, so I'm just content that it works. I was very surprised by how much hyperparameter finagling I had to do to get the DLGN converging; the tiny relu network I trained at the beginning, in comparison, converged with dead-simple SGD in a third of the epochs. The speedup was surprising in the sense that the bit-level parallelism fell out naturally: that 64× speedup alone was unexpected and pretty sweet. There's likely still a lot of speed left on the table. I just did the bare minimum to get the C code working: it's single-threaded, there's no vectorization, lots of register spilling, etc. Imagine the speedup you'd get running the circuit on e.g. an FPGA. But no, it was not surprising in the sense that yeah, multiplying billions of floats is going to be much slower than a handful of parallel bitwise ops. Physics is physics, doesn't matter how good your optimizer is.
  - jgord 1y ago
    what percentage of ops were passthru ? ps. superb writeup and project
    - isaacimagine 1y ago
      Thank you! Good question, Here are the NN stats, before lowering to C: total gates | 2303 | 100.0% -------------------+------+------- passthrough | 2134 | 92.7% gates w/ no effect | 1476 | 64.1% Note the rows aren't mutually exclusive.
Twirrim 1y ago
You've made some mistakes with the Game of Life rules. You've missed out the overpopulation rule: Any live cell with more than three live neighbours dies Nit: > I guess there’s a harsh third rule which is, “if the cell is dead, it stays dead”. That phrasing is inaccurate, if a dead cell stayed dead, the first rule wouldn't work. I'm not sure that particular sentence adds much to the flow, honestly.

randomtoast 1y ago

Given the complexity of modern compiler optimizations, integrating a small neural network into a C compiler like GCC might help generate faster executable code by guiding optimization decisions.

nurettin 1y ago
-O3 -march=native is pretty much all you need and the rest is marginal or circumstantial.
- randomtoast 1y ago
  What makes you so confident that an AI-assisted compiler couldn't significantly enhance optimizations? A relevant example of a complex problem where neural networks have improved performance is found in chess engines. Today, top-level engines like Stockfish have integrated NNUE ("Efficiently Updatable Neural Network") which has significantly boosted their performance.
  - nurettin 1y ago
    What makes me confident is the fact that I've been using gcc since 2.95 (well redhat had its patched "2.96" but yeah) so I witnessed the evolution of these parameters. What makes neural networks and learning irrelevant is because there aren't a billion parameters, most parameters don't depend on each other. It is not a search problem. You have the wrong domain. This is like saying "hey let's crack that password using neural networks, stockfish is so advanced!" And people have tried auto searching parameters, the results were as I described in my response. Moreover, imagine releasing code and having cluebies complain about trying to make it go faster with -fomit-frame-pointer. The whole idea is wasteful and cringe.
- queuebert 1y ago
  That doesn't fix suboptimal algorithm choices, but neither would a small NN in the compiler. A big NN could rewrite large sections of code without changing the logic, but why do that during translation instead of rewriting the source?

godelski 1y ago

> I tried something new for the first time, which was to keep a journal during development. DO THIS!!! I cannot stress this enough! If you work in a professional science lab, say, physics, biology, chemistry, you are expected to keep an experiment journal. It provides more help to you than the company too (knowledge dump, liability, etc). I can't tell you how many times some stupid ass seemingly benign comment saved my behind. They're worth their weight in gold. For ML experiments I use wandb and hydra[0]. Put all your configs into hydra. Be fucking pedantic. You should log your seeds, versions, the date, and I mean everything. It only takes a few extra minutes to set this up but the one time you need it it'll save you hours. Dump all that into wandb AND your model checkpoints. You will forget what that checkpoint corresponds to. Make liberal use of wandb tags and comments (through hydra you can make these cli arguments to automate even if launching from slurm scripts). Turn on wandb's code saving. Most importantly, use those notebooks wandb gives you. Don't worry if it gets messy. It's a experiment notebook, it'll get messy. You'll get better with experience and as you find your style. It sounds like a lot of work but it really isn't. You can get this all done under 20 minutes and if you write it right you can just copy paste it moving forward (i.e. yeah, make a personal library). I can PROMISE you that one mishap will far outweigh this extra work. You look like a pretentious perfectionist but really I'm a lazy piece of shit rust doesn't want to spend hours or days debugging some stupid mistake I'm too dumb or tired to catch. The extra benefit is when shit world you can spin up some (wandb) sweeps and go do some other thing that's always behind. (On topic, stop using personal wandb accounts for your work experiments. They're like the best company out there, get your boss to pay. They provide an amazing service and are a delight to work with. I cannot speak highly enough about them. They're not the company you want to mooch from. I've literally seen this happen while working for a top 3 market cap which was already paying for seats and you just needed to send a slack message to one dude... not cool guys... not cool...) [0] https://hydra.cc/docs/intro/ https://hydra.cc/docs/intro/

0cf8612b2e1e 1y ago
From my two minute skim of the docs, not encouraging that hydra only officially supports up to Python 3.11.
- 1y ago

nine_k 1y ago

The interesting thing here is that it's not a straightforward port. JAX is already very fast, for the architecture it implements. The point is that the network is heavily contracted by removing nodes that only do pass-through, and then hugely parallelizing the computations using bitwise operations on 64 bits at once. Hence this incredible speedup.

JonChesterfield 1y ago

If you replace the uint64_t cell with an attribute((vector_size(32))) and build with march=native, the bitwise ops will work exactly as before but you'll light up the vector units on the x64 machine. Good blog post, thanks!

isaacimagine 1y ago
Glad you enjoyed it, and thanks for the tip!

hermitShell 1y ago

This is very fascinating as a limit case, which always serve as a good example of the bound. I think it highlights that “efficiency isn’t everything” just like in so many other systems like healthcare and justice. In this case we could figure out the activation functions by analysis, which is impossible for problems of higher dimensionality. The magic of AI isn’t in it’s efficiency, it’s in making things computable that simply aren’t by other means.

gwern 1y ago

How much of a speedup is the C compiler optimization able to achieve in terms of compiling it down to a hand-written C equivalent vs the -O0 non-optimized assembler? What does the optimized C/assembler do which isn't actually necessary and accounts for the remaining inefficiency?

isaacimagine 1y ago
There are 163 lines of C. Of them, with -O3, 104 lines are present in the assembly output. So the C compiler is able to eliminate an additional ~36.2% of the instructions. It doesn't do anything fancy, like autovectorization. I profiled just now: | instrs (aarch64) | time 100k (s) | conway samples (%) | | -O0 | 606 | 19.10s | 78.50% | | -O3 | 135 | 3.45 | 90.52% | The 3.45s surprises me, because it's faster than the 4.09s I measured earlier. Maybe I had a P core vs an E core. For -O0, the compiler is emitting machine code like: 0000000100002d6c ldr x8, [sp, #0x4a0] 0000000100002d70 ldr x9, [sp, #0x488] 0000000100002d74 orn x8, x8, x9 0000000100002d78 str x8, [sp, #0x470] Which is comically bad. If I try with e.g. -Og, I get the same disassembly as -O3. Even -01 gives me the same disassembly as -O3. The assembly (-0g, -01, -03) looks like a pretty direct translation of the C. Better, but also nothing crazy (e.g. no autovectorization): 0000000100003744 orr x3, x3, x10 0000000100003748 orn x1, x1, x9 000000010000374c and x1, x3, x1 0000000100003750 orr x3, x8, x17 Looking more closely, there's actually surprisingly little register spilling. I think the real question you're asking is, as I wrote: > If we assume instruction latency is 1 cycle, we should expect 2,590 fps. But we measure a number nearly 10× higher! What gives? Part of this is due to counting the instructions in the dissassembly wrong. In the blogpost I used 349 instructions, going off Godbolt, but in reality it's 135. If I redo the calculations with this new numbers, I get 2.11 instructions per bit, 0.553 million instrs per step, dividing out 3.70 gcycles/s gives 6,690 fps. Which is better than 2,590 fps, but still 3.6x slower than 24,400. But I think 3.6x is a factor you can chalk up to instruction-level parallelism,. Hope that answers your questions. Love your writing Gwern.
- gwern 1y ago
  Thanks for checking. It sounds like the C compiler isn't doing a great job here of 'seeing through' the logic gate operations and compiling them down to something closer to optimal machine code. Maybe this is an example of how C isn't necessarily great for numerical optimization, or the C compiler is just bailing out of analysis before it can fix it all up. A fullstrength symbolic optimization framework like a SMT solver might be able to boil the logic gates down into something truly optimal, which would then be a very interesting proof of concept to certain people, but I expect that might be for you an entire project in its own right and not something you could quickly check. Still, something to keep in mind: there's an interesting neurosymbolic research direction here in training logic gates to try to extract learned 'lottery tickets' which can then be turned into hyper-optimized symbolic code achieving the same task-performance but possibly far more energy-efficient or formally-verifiably.

hy4000days 1y ago

[dead]

thirtygeo 1y ago

That approach is bananas! I had seen the source inspiration paper from Google but it's need to see it replicated and extended so shortly after.

isaacimagine 1y ago
+10 respect, thank you <3

gomoboo 1y ago

Relevant post from a few years ago: https://news.ycombinator.com/item?id=25290112 https://news.ycombinator.com/item?id=25290112 “ NN-512 is an open-source Go program that generates fully AVX-512 vectorized, human-readable, stand-alone C implementations of convolutional neural nets”

Vox_Leone 1y ago

Well done — really enjoyed this. We could use this kind of optimization in our library[0], which builds differentiable logic networks out of gates like AND, XOR, etc. It focuses on training circuit-like structures via gradient descent using soft logic semantics. The idea of compiling trained models down to efficient bit-parallel C is exactly the kind of post-training optimization we’ve been exploring — converting soft gates back into hard boolean logic (e.g. by thresholding or symbolic substitution), then emitting optimized code for inference (C, WASM, HDL, etc). The Game of Life kernel is a great example of where logic-based nets really shine. [0]https://github.com/VoxLeone/SpinStep/tree/main/benchmark https://github.com/VoxLeone/SpinStep/tree/main/benchmark

jjaksic 1y ago

Cool. If you do this with an LLM, someone will pay you a lot of money.

kookamamie 1y ago

> 1,744x speedup Is that 1744x or 1.7x?

genewitch 1y ago
Former, also there's too many digits of precision for it to be the latter.

mickey475778 1y ago

[dead]

pjmlp 1y ago
Or any other strongly typed natively compiled language for that matter.

Lopezkatheryn 1y ago

[dead]

andy12_ 1y ago

I also worked a long time ago in recreating the original Deep Differentiable Logic Network paper [1], so I have a couple of additions to make. > I wanted to see if I could learn the wires in addition to the gates. I still think it’s possible, but it’s something I had to abandon to get the model to converge. Actually, I read some other paper where they also learned the wiring, but they did so by alternating the training of the gates and the wires (in some iterations they learned the wiring while keeping the gates frozen, and in other they learned the gates while keeping the wiring frozen). The problem with this approach is that it is inherently non-escalable: you need a lot of gates to approximate the behavior of a simple MLP, and if you need a full NxM learned matrix to encode the wiring, the memory needed to learn, for example, MNIST, gets huge, quickly. I think that for this there are 2 fixes: - You actually don't need to learn a full NxM matrix to increase the expressivity of the network. You can, for each output gate, select a random subset of possible input gates of size K, and then you only need a learned matrix of size KxM. I did the numbers, and even a moderately small K, like 16 or 32, wildly increases the number of circuits you can learn with a smaller number of layers and gates. - You could use a LoRA kind of matrix. Instead of a matrix NxM, use a pair of matrices NxK and KxM, where K<<N,M. Learning the wiring also has other benefits. As the output gate can learn to swap the inputs if needed, you can remove some learnable gates that are "mirrors" or "permutations" of each other (a and not b, not a and b; a or not b, not a or b), which can help scale the networks to use gates of more inputs (I tried with 3-input gates and 4-input gates). Also, as the author pointed out, it was very difficult to get the models to converge. It was very frustrating that I never managed to get a working model that performed really well on MNIST. In the end, I gave up on that and I worked on how to make the network consistently learn simple 3-input or 4-input functions with perfect accuracy, and I managed to make it learn them consistently with a couple dozen iterations, which was nice. [1] https://arxiv.org/abs/2210.08277 https://arxiv.org/abs/2210.08277

isaacimagine 1y ago
Very cool, thank you for sharing!