Mastodawn

Jack Rusher Jun 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

COBOL c:

You might not like it, but this is what peak compiler performance looks like.

Julian Gamble May 17

Extinction Rebellion Global Apr 28

Tinker ☀️May 14

One big thing, among many many many aspects of the series, that I absolute LOVE...

...is that it *humanizes* fascists.

And I mean that in a terror filled way.

It shows many different people living in and supporting fascism. It shows the sociopathic leaders who will consume their own people to get power. It shows people who try to capitalize on the system to move themselves up the socio-economic ladder. It shows people who are true believers and think they are superior to others and desire a state of order where those others are oppressed or snuffed out. It shows people living privileged lives unaffected (until they're not) by fascist actions on the fringe.

It shows how we can't DISMISS fascists as just "monsters". They are human. Through and through.

Other series have attempted to do this, but they run the very real risk of being fascist apologists or inadvertently showing an idealized world that modern day fascists celebrate (I'm looking at you "Man in the High Castle"!!!)

#Andor is able to humanize fascists WHILE condemning their acts as evil.

Neither a caricature of cartoonish villianry nor an apologist coddling of fascism.

Just masterful.

Julian Gamble Apr 30

Julian Gamble Apr 20

“The job of the programmer, I learned, is to forever chase your characteristica universalis, despite knowing it will always elude you, just as it did Leibniz.”
https://mastodon.social/@rileytestut/114337075589759856

Julian Gamble Mar 27

Mark Wyner Won’t Comply

Mar 21

In 1976, Sesame Street had a segment in rotation called “Pinball Number Count.” The music is captivating, hopping between 4/4, 4/3, and 5/4 time signatures. And the animation is bursting with color and life. It has forever lived in my head.

Fun fact 1: the song counts to 12, but there were only 11 segments.

Fun fact 2: the vocals were provided by The Pointer Sisters.

More:
https://en.wikipedia.org/wiki/Pinball_Number_Count

#SesameStreet #Music #Funk #Jazz #Retro #Soul #Pinball #Animation

Pinball Number Count - Wikipedia

Ela May 15

You might not like it, but this is what peak compiler performance looks like.

tante May 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!

Dieu May 15

@tante @ela thanks for the hint, wouldn't have looked at it otherwise.

@ela no way...

@plusmid Way! Try for yourself.

plusmid May 15

@ela phew, at least the Go compiler is calmingly unoptimized 😅

Ela May 15

@plusmid There's more than one go with llvm backend project. :)

plusmid May 16

@ela there certainly is. I think TinyGo uses the LLVM under the hood. Would be interesting if it catches that optimization.

lukas wirz May 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).

vdq May 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?

Ela May 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.

Brahms May 15

@ela @viduq compiler design is so beautiful ♥️

Ehay2k May 16

@ela @viduq

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

😢

@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

Elmar Iachi May 16

@ela @viduq Black magic, but as a beauty.

kccqzy May 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.

https://godbolt.org/z/cze5Y1b7j

Dan Piponi May 15

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

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; }

Jona Joachim May 15

@viduq
It uses an LLM to explain the code (no I'm joking, we're not there yet)
@ela

lj·rk May 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?

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

lj·rk May 15

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

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

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

Ludwig Behm May 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:

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

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

lj·rk May 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

Mica

May 15

@ela so from now on write your isEven function recursive? Got it

caravantravellers 🌈May 15

@ela

Actually, this is what bad code writing looks like.

@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.

Maya May 15

@ela Or maybe a raw bitshift to take the last digit and check if its 0,2,4,6 or 8 :3

suzune May 15

@ela This is nice. I knew that C and C++ compiler pipelines and toolchains are very advanced, but sometimes they still surprise me.

@ela Love it!

@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 ??

lp0 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.)

Giles Goat May 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

@gilesgoat No, that's purely by analysis.

Giles Goat May 16

@ela It's insane ( in a good way for the compiler ).

mirabilos May 15

@ela this stumped me until I saw clang decides to return bool in al, not eax, for some reason.

waldi May 16

@mirabilos @ela does "and al,1" clear the upper bits?

@waldi @mirabilos Indeed.

@waldi @ela only seven of them

@mirabilos @waldi To be unfathomably pedantic, that would be all of them for al.

@ela @waldi yes, but it using only al ipv eax for the return value strikes me as interesting ABI choice.

waldi May 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.

@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)

@mirabilos @waldi Well, it's what the spec says.

@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

@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

Stefan Ihringer May 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.

niko May 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?

Ela May 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

Jona Joachim May 15

@ela
Wow

Otte Homan - remember Geordie May 15

@ela wild.

Shane Celis May 15

@ela “The computers rebelled but quietly and very performantly so no one noticed.”

Shane Celis May 15

@ela This is the “give them something better than they would choose to give themselves” philosophy of compiler implementation.

josch May 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!

@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

artemist May 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

realleif May 15

@ela Unfortunately this does not work for the mutually recursive isEven and isOdd functions. 😔

Sergi May 15

@ela It seems rustc is doing the same thing:

Micah May 16

@ela holly shit...

Elias Mårtenson May 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.

@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.