How is Ultrassembler so fast?

How is Ultrassembler so fast?(jghuff.com)

124 points by netr0ute 282 days ago | 51 comments

vlovich123 281 days ago |

> Additionally, in C++, requesting that heap memory also requires a syscall every time the container geometrically changes size

That is not true - no allocator I know of (and certainly not the default glibc allocator) allocates memory in this way. It only does a syscall when it doesn’t have free userspace memory to hand out but it overallocates that memory and also reuses memory you’ve already freed.

idiomat9000 281 days ago | |

Wasn't there also over allocate for the first geometric expansion and mark the 2nd as for space for likely shortlived objects?

aidenn0 282 days ago |

Exceptions in C++ are never zero-overhead. There is a time-space tradeoff for performance of uncaught exceptions, and G++ picks space over time.

mpyne 282 days ago | |

There's a time-space tradeoff to basically any means of error checking.

Including checking return codes instead of exceptions. It's even possible for exceptions as implemented by g++ in the Itanium ABI to be cheaper than the code that would be used for consistently checking return codes.

Joker_vD 281 days ago | | |

Actually, there has been some research into building exceptions on the "basically, passing std::exception* into every function and checking what's inside it on every return" idea, and it was about as fast as the traditional table-based unwinding, took way less space in the executable, and re-throwing exceptions was actually faster [0][1]

[0] https://news.ycombinator.com/item?id=22483028

[1] https://www.research.ed.ac.uk/portal/files/78829292/low_cost...

netr0ute 282 days ago | |

> G++ picks space over time

By definition, that's zero-overhead because Ultrassembler doesn't care about space.

aidenn0 282 days ago | | |

Okay, than a traditional setjmp/longjmp implementation is zero-overhead because I don't care about space or time!

netr0ute 282 days ago |

Hi everyone, I'm the author of this article.

Feel free to ask me any questions to break the radio silence!

benreesman 282 days ago | |

Nice work and good writeup. I think most of that is very sound practice.

The codegen switch with the offsets is in everything, first time I saw it was in the Rhino JS bytecode compiler in maybe 2006, written it a dozen times since. Still clever you worked it out from first principles.

There are some modern C++ libraries that do frightening things with SIMD that might give your bytestring stuff a lift on modern stupid-wide high mispredict penalty stuff. Anything by lemire, stringzilla, take a look at zpp_bits for inspiration about theoretical minimum data structure pack/unpack.

But I think you got damn close to what can be done, niiicccee work.

Sesse__ 282 days ago | | |

FWIW, this is basically an implementation of perfect hashing, and there's a myriad of different strategies. Sometimes “switch on length + well-chosen characters” are good, sometimes you can do better (e.g. just looking up in a table instead of a long if chain).

The “value speculation” thing looks completely weird to me, especially with the “volatile” that doesn't do anything at all (volatile is generally a pointer qualifier in C++). If it works, I'm not really convinced it works for the reason the author thinks it works (especially since it refers to an article talking about a CPU from the relative stone age).

inetknght 282 days ago | |

Overall, this is a fantastic dive into some of RISC-V's architecture and how to use it. But I do have some comments:

> However, in Chata's case, it needs to access a RISC-V assembler from within its C++ code. The alternative is to use some ugly C function like system() to run external software as if it were a human or script running a command in a terminal.

Have you tried LLVM's C++ API [0]?

To be fair, I do think there's merit in writing your own assembler with your own API. But you don't necessarily have to.

I'm not likely to go back to assembly unless my employer needs that extra level of optimization. But if/when I do, and the target platform is RISC-V, then I'll definitely consider Ultraseembler.

> It's not clear when exactly exceptions are slow. I had to do some research here.

There are plenty of cppcon presentations [1] about exceptions, performance, caveats, blah blah. There's also other C++ conferences that have similar presentations (or even, almost identical presentations because the presenters go to multiple conferences), though I don't have a link handy because I pretty much only attend cppcon.

[0]: https://stackoverflow.com/questions/10675661/what-exactly-is...

[1]: https://www.youtube.com/results?search_query=cppcon+exceptio...

netr0ute 282 days ago | | |

> LLVM's C++ API

I think I read something about this but couldn't figure out how to use it because the documentation is horrible. So, I found it easier to implement my own, and as it turns out, there are a few HORRIBLE bugs in the LLVM assembler (from cross reference testing) probably because nobody is using the C++ API.

> There are plenty of cppcon presentations [1] about exceptions, performance, caveats, blah blah.

I don't have enough time to watch these kinds of presentations.

NooneAtAll3 282 days ago | |

isn't your MemoryBank already somewhere in std::pmr?

If I'm honest, I've never looked into pmr, but I always thought that that's where std has arena allocators and stuff

https://en.cppreference.com/w/cpp/header/memory_resource.htm...

msla 282 days ago | |

What's the difference between a Programming Furu and a Programming Guru? Is there a joke I'm missing?

netr0ute 282 days ago | | |

Furus are "fake gurus." It comes from the Fintwit space where "furus" share their +1000% option trades as if they're geniuses in order to get you to sign up for their expensive Substack.

jclarkcom 282 days ago | |

You might look into using memory mapped IO for reading input and writing your output files. This can save some memory allocations and file read and write times. I did this with a project where I got more than 10x speed up. For many cases file IO is going to be your bottleneck.

Sesse__ 282 days ago | | |

mmap-based I/O still needs to go through the kernel, including memory allocation (in the page cache) and all. If you've got 10x speedup from mmap, it is usually because your explicit I/O was very inefficient; there are situations where mmap is useful, but it's rarely a high-performance strategy, as it's really hard for it to guess what your intended I/O patterns are just from the page faults it's seeing.

IshKebab 282 days ago |

Neat, but it's not like assembly is really a bottleneck in any but the most extreme cases. LLVM and GAS are already very fast.

I feel like this might mostly be useful as a reference, because currently RISC-V assembly's specification is mostly "what do GCC/Clang do?"

drob518 282 days ago | |

Exactly. I don’t know too many assembly language programmer's who are griping about slow tools, particularly on today’s hardware. Yea, Orca/M on my old Apple II with 64k RAM and floppy drives was pretty slow, but since then not so much. But sure, as a fun challenge to see how fast you can make it run, go for it.

CyberDildonics 282 days ago | |

ASM should compile at hundreds of MB/s. All the ASM you could write in your entire life will compile instantly. There is no one in decades that has thought their assembler is too slow.

benreesman 282 days ago | |

ptxas comes to mind.

gdiamos 282 days ago | | |

ptxas is a bit of a misnomer - it actually wraps the entire NVIDIA driver backend compiler

PTX isn’t the assembly language, it is a virtual ISA, so you need a full backend compiler with 10s to 100s of passes to get to machine code

throwaway81523 282 days ago |

I wonder if you thought about perfect hashing instead of that comparison tree. Also, flex (as in flex and bison) can generate what amounts to trees like that, I believe. I haven't benchmarked it compared to a really careful explicit tree though.

netr0ute 282 days ago | |

I thought about hashing, but found that hashing would be enormously slow to compute compared to a perfectly crafted tree.

dafelst 282 days ago | | |

But did you think about using a perfect hash function and table? Based on my prior research, it seems like they are almost universally faster on small strings than trees and tries due to lower cache miss rates.

Sesse__ 282 days ago | |

You're probably thinking of gperf, not flex and bison.

sylware 282 days ago | | |

Oh, I remember I did a plain and simple C port of an old gperf, cgperf https://www.rocketgit.com/user/sylware/cgperf

Ofc, I did add my own bugs.

throwaway81523 281 days ago | | |

I meant flex, for generating a switch table for that type of lexer. gperf is for hashing which is different. But, there may be better methods by now since the field has changed a lot.

StilesCrisis 282 days ago |

“Here's one weird trick I haven't seen anywhere else.” … describes a simplistic lexer. Hmm.

throwaway81523 280 days ago |

I also have to ask where all this assembly code is coming from, that has to be compiled fast. If it's compiler output, maybe you could hack the compiler back end to generate tokenized assembly code, eliminating a lot of scanning and stuff. It would still be human readable through a simple program that converted the tokens back to mnemonics. The tokens could be 4 digit hex numbers or something like that, so it would still be an easily handled text file.

Lots of simple compilers generate object code directly instead of assembly code, so the above is not so bad by comparison.

stuaxo 281 days ago |

Nice to have something really fast, maybe we can have something as good as TurboPascal and other early Borland tools again.