Julian Gamble

@juliansgamble@techhub.social
65 Followers
107 Following
212 Posts
Devops, Docker and CD. Java Veteran.
Financial Services System Engineering. Author.
Websitehttps://juliangamble.com/
Julian GambleJul 8
@NanoRaptor that’s pretty good for a stream of thought. Perhaps try some more with other Spielberg movies, or some James Cameron?
Julian GambleJul 8
vfigJul 5
@NanoRaptor
Julian GambleJun 24
fogusJun 18
As we strive to build computers to pass the Turing Test, we strive to build people who fail it.
Julian GambleJun 17
Niki TonskyJun 12
A bit of common sense for you https://tailscale.com/blog/frequent-reath-security
Frequent reauth doesn't make you more secure

Securely connect to anything on the internet with Tailscale. Built on WireGuard®️, Tailscale enables you to make finely configurable connections, secured end-to-end according to zero trust principles, between any resources on any infrastructure.

Show threadJulian GambleJun 14
@tarkasteve ?
Julian GambleJun 10
Show threadJack RusherJun 3
@fogus “In 3-8 years we'll have a machine with the general intelligence of an average human being. The machine will begin to educate itself with fantastic speed. In a few months it will be at genius level and a few months after that its powers will be incalculable.”
—Marvin Minsky, 1970
Show threadJulian GambleJun 3
@bodil so if not Rust, what are you coding in now?
Show threadJulian GambleMay 22
@bodil There were lots of good things about it.
Julian GambleMay 22
Toromino  May 19
COBOL c:
Julian GambleMay 19
ElaMay 15
You might not like it, but this is what peak compiler performance looks like.
×
ElaMay 15
You might not like it, but this is what peak compiler performance looks like.
Show threadtanteMay 15
@ela I love how the ALT text really explains what's going on even for people not super familiar with machine code. Shows how helpful that feature is for everyone. Thank you!
Show threadDieuMay 15
@tante @ela thanks for the hint, wouldn't have looked at it otherwise.
Show threadplusmidMay 15
@ela no way...
Show threadElaMay 15
@plusmid Way! Try for yourself.
Show threadplusmidMay 15
@ela phew, at least the Go compiler is calmingly unoptimized 😅
Show threadElaMay 15
@plusmid There's more than one go with llvm backend project. :)
Show threadplusmidMay 16
@ela there certainly is. I think TinyGo uses the LLVM under the hood. Would be interesting if it catches that optimization.
Show threadlukas wirzMay 15
@ela Interestingly clang does not think that "bool isEven(unsigned int i) {return i%2==0;}" should yield the same assembly, while gcc compiles the above to the same assembly as clang does for your function (except for one register).
Show threadvdqMay 15
@ela how can the compiler break down a recursive function to a mathematical statement? There is no brute force involved or is there? And does it do that only when optimizations are on?
Show threadElaMay 15
@viduq It's not exactly brute force, but it does involve some heavy lifting in the optimizer. Tail recursion elimination turns the recursive calls into a loop. Then, induction variables of the loop are detected, and finally strength reduction, algebraic simplification finish it off.
Show threadBrahmsMay 15
@ela @viduq compiler design is so beautiful ♥️
Show threadEhay2kMay 16

@ela @viduq

Uh, I need Alt text to help me understand this.

😢

Show threadElaMay 16
@Ehay2k @viduq alt text is right here: https://archive.org/details/advancedcompiler00much
Advanced compiler design and implementation : Muchnick, Steven S., 1945- : Free Download, Borrow, and Streaming : Internet Archive

Includes bibliographical references (p. 801-820) and indexes

Internet Archive
Show threadElmar IachiMay 16
@ela @viduq Black magic, but as a beauty.
Show threadkccqzyMay 16
@ela @viduq It's not a tail recursion. There's a boolean not after the recursive call. That makes the feat even more amazing.
Show threadDan PiponiMay 15

@viduq @ela Check out how examples like this are also reduced to simple polynomials without loops:

https://godbolt.org/z/cze5Y1b7j

The -1431655764 is pretty fiendish if you've not met that trick before.

Compiler Explorer - C++ (x86-64 clang (trunk))

int sum(unsigned int i) { if (i == 0) { return 0; } return sum(i - 1) + 2 * i * i; }

Show threadJona JoachimMay 15
@viduq
It uses an LLM to explain the code (no I'm joking, we're not there yet)
@ela
Show threadlj·rkMay 15
@ela Nice! I wonder how this feat is performed? I suppose the tail-call is eliminated, and the resulting loop is reasoned about, perhaps unrolled even and then some analysis turns up this?
Show threadlj·rkMay 15

@ela ah whelp u answered this while I was typing :'D

https://infosec.exchange/@ela/114512429688903239

Ela (@ela@infosec.exchange)

@viduq@mstdn.social It's not exactly brute force, but it does involve some heavy lifting in the optimizer. Tail recursion elimination turns the recursive calls into a loop. Then, induction variables of the loop are detected, and finally strength reduction, algebraic simplification finish it off.

Infosec Exchange
Show threadLudwig BehmMay 15

@ljrk @ela the truly amazing thing about compiler explorer with clang is, that it can even give you every important step of the optimization pipeline:

https://clang.godbolt.org/z/dvhs93z5f

Compiler Explorer - C++ (x86-64 clang (trunk))

bool isEven(unsigned int i) { if (i==0) return true; return !isEven(i - 1); }

Show threadlj·rkMay 15
@lbehm @ela Wow, I didn't even know that! I knew that clang has this feature but it's kinda pain to use, but this is reaaaally accessible! wow
Show threadMica May 15
@ela so from now on write your isEven function recursive? Got it ​​
Show threadcaravantravellers 🌈May 15

@ela

Actually, this is what bad code writing looks like.

Show threadElaMay 16
@caravantraveller This might be an extreme case of bad code, yes. But the moral of the story is to always prefer readability, maintainability and correctness, unless you have measurements to support a case of having to optimize manually.
Show threadMayaMay 15
@ela Or maybe a raw bitshift to take the last digit and check if its 0,2,4,6 or 8 :3
Show threadsuzuneMay 15
@ela This is nice. I knew that C and C++ compiler pipelines and toolchains are very advanced, but sometimes they still surprise me.
Show threadNiels MoseleyMay 15
@ela Love it!
Show threadGiles GoatMay 15
@ela This is INSANE .. I mean it's insane the C code written could not be worse than that !! .. But it's 10 times more insane the compiler realized what was meant to be and put the best solution ( i.e. 'mod 2' ) .. Did it guess by the NAME of the function the intended purpose maybe ??
Show threadlp0 on fire May 15

@gilesgoat @ela, it's not “i % 2”, as that would give an inverted result. It's either “~i & 1” or “1 & ~i”, depending on the output assembly code. Here it is, for 32-bit ARM:

MOV r1, #1
BIC r0, r1, r0
BX lr

(BIC is bit-clear, essentially AND NOT.)

Show threadGiles GoatMay 16
@lp0_on_fire @ela yes but if you want an isODD(x) that returns '1' if it's odd and '0' if not AND 01 will suffice, if you want the reverse you can do (NOT(X)) AND 01
Show threadElaMay 16
@gilesgoat No, that's purely by analysis.
Show threadGiles GoatMay 16
@ela It's insane ( in a good way for the compiler ).
Show threadmirabilosMay 15
@ela this stumped me until I saw clang decides to return bool in al, not eax, for some reason.
Show threadwaldiMay 16
@mirabilos @ela does "and al,1" clear the upper bits?
Show threadElaMay 16
@waldi @mirabilos Indeed.
Show threadmirabilosMay 16
@waldi @ela only seven of them
Show threadElaMay 16
@mirabilos @waldi To be unfathomably pedantic, that would be all of them for al.
Show threadmirabilosMay 16
@ela @waldi yes, but it using only al ipv eax for the return value strikes me as interesting ABI choice.
Show threadwaldiMay 16
@mirabilos @ela Ah, because _Bool is defined as 8bit value where only bit 0 matters, bits 1 to 7 are set to 0 and 8 to 63 are undefined.
Show threadmirabilosMay 16
@waldi @ela except for actual storage (where one bit would be better in structs for example), blowing it up to the full 32 bits would reduce the number of instructions executed overall in typical programs (and incidentally even the code size)
Show threadElaMay 16
@mirabilos @waldi Well, it's what the spec says.
Show threadmirabilosMay 16
@ela @waldi I admit only vague familiarity with the psABI for amd64 (normally preferring i386), and specifically not that they chose a (surprising, to me) representation for booleans
Show threadXenotarMay 15
@ela @naoEhAlexa
Show threadcassieMay 15
@ela I wrote a blog post years ago that shows all the intermediate steps of performing this optimization: https://blog.witchoflight.com/2018/llvm-hearts-peano-addition/
LLVM 💖s Peano Addition

I am surprised to discover that LLVM can optimize the standard peano definition of addition, so I set out to investigate.

Witch of Light
Show threadStefan IhringerMay 16
@porglezomp @ela very cool. I have no idea about compiler internals but were able to follow this thanks to the step by step C equivalents.
Show threadnikoMay 17
@porglezomp @ela you start with the tail recursion optimization but here isEven is very clearly not tail recursive. Do you know how LLVM handles that?
Show threadElaMay 17

@nrab @porglezomp LLVM extends that basic algorithm a tad bit by trying to move instructions between the call and the return to the top of the generated loop. In cases in which this isn't trivially true (like for code neither depending on the function call value nor having an influence on the return value), there is one additional trick. If the operation performed on the return value of the function call is a commutative and associative operation, it can be eliminated using accumulator recursion elimination.

The code lives here: https://github.com/llvm/llvm-project/blob/main/llvm/lib/Transforms/Scalar/TailRecursionElimination.cpp#L658

llvm-project/llvm/lib/Transforms/Scalar/TailRecursionElimination.cpp at main · llvm/llvm-project

The LLVM Project is a collection of modular and reusable compiler and toolchain technologies. - llvm/llvm-project

GitHub
Show threadJona JoachimMay 15
@ela
Wow
Show threadOtte Homan - remember GeordieMay 15
@ela wild.
Show threadShane CelisMay 15
@ela “The computers rebelled but quietly and very performantly so no one noticed.”
Show threadShane CelisMay 15
@ela This is the “give them something better than they would choose to give themselves” philosophy of compiler implementation.
Show threadjoschMay 15
@ela This is brilliant! I'd like to put this into my uni lecture on C/C++. If you would like to be credited for this find, how would you like to be attributed? Thanks!
Show threadElaMay 16

@josch This code snipped has been floating around for a while, here's a blog post from a few years ago talking about it that seems to be the original source: https://www.notion.so/mjbo/Exploring-Clang-LLVM-optimization-on-programming-horror-acd2bb52dd934d9c9a76150484f3b64f

Credit them. :)

Exploring Clang/LLVM optimization on programming horror | Notion

Recently, I've come across a not so efficient implementation of a isEven function (from r/programminghorror).

mjbo on Notion
Show threadartemistMay 15
@ela it seems like the transform for this happens the IndVarSimplifyPass llvm optimizer pass, and the math for that is implemented in ScalarEvolutionExpander.cpp
llvm-project/llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp at llvmorg-20.1.5 · llvm/llvm-project

The LLVM Project is a collection of modular and reusable compiler and toolchain technologies. - llvm/llvm-project

GitHub
Show threadrealleifMay 15
@ela Unfortunately this does not work for the mutually recursive isEven and isOdd functions. 😔
Show threadSergiMay 15
@ela It seems rustc is doing the same thing:
Show threadMicahMay 16
@ela holly shit...
Show threadElias MårtensonMay 16

@ela This is quite impressive, and I wonder how complex you could make these kinds of functions while still having this kind of optimisation happening.

But it does make me ask: Should perhaps the compiler warn about these cases? I mean, it's great that the compiler can optimise it, but when it can, the code should probably be simplified, and that would be better than relying on the compiler.

Show threadElaMay 16

@loke The problem here is that the compiler can't tell if something is just an idiomatic expression or bad coding. In fact, such warnings might even distract programmers from getting things right.

It's very important to keep in mind that source code has a dual purpose. Yes, it instructs the computer what to do, but computers are perfectly fine with machine instructions. Much more importantly, source code exists for humans to read, understand and reason about.

Premature optimization is the root of all evil. The primary goals of writing code must be correctness and readability, with correctness often being influenced by readability.

Sure, some code needs to be super fast. Your interrupt handler for that 10GB network card? This code doing the task switching in your OS? Absolutely. Every cycle counts. But in order to achieve this, you need to measure. I've seen a lot of theories about performance improvements collide hard with the realities of modern CPU and compiler architecture. Always profile, always measure, always benchmark.

And for that precious lines of code, modern compilers are happy to infodump on you every step they take.

Show threadMorten GrøftehaugeMay 16

@ela @loke There's a lot of examples of this. Like mergesort vs quicksort (yes, no one uses vanilla quicksort but I would argue that it's closer to quick than merge). And then in network science you have these algorithms where runtime is around cubic and whether quadratic, cubic or tertiary is the right choice very much depends on the properties of your graph, like actual size, rather than what happens when n goes towards infinite.

Edit: urgh, I'm being a reply guy. Sorry. Graphs are neat.