Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Inverting a binary tree using x64 assembly

sanket.tech

Post reply on HN
Print view View original

21–30 of 73 posts

Re: Inverting a binary tree using x64 assembly

#21

Post by danbruc »

pyinstallwoes wrote: post #20
danbruc wrote: post #15

Assume RAX points to the root node and nodes just contain two child pointers and everything is aligned and whatever. :invert cmp rax, 0 jnz swap: ret :swap push rax mov rax, [rax] call invert mov rbx,[rsp] xchg rax, [rbx+8] mov [rbx], rax call invert pop rax ret The last time I used an assembler was before x86-64 was invented, I am not even sure I ever used one in protected mode. But that seems a totally reasonable w…

Did you write Forth at all?

No. Why do you ask?

EDIT: As Wikipedia describes it as a stack-oriented language, because of my comment about putting everything onto the stack?

Re: Inverting a binary tree using x64 assembly

#22

Post by sedatk »

_8j50 wrote: post #11
cgh wrote: post #10

> I will be using x64 assembly with the AT&T syntax as it is objectively superior than the Intel syntax. This made me laugh because it must be a reference to this: https://news.ycombinator.com/item?id=33652023 > I contend that the AT&T syntax is harmful and bad, and should never be used, for any reason, under any circumstances, by anyone.

AT&T really is annoying but it feels like the big vs little endian debate. Fairly easy to convert between the two as well.

For those who don't know, that's why big and little endian were called that, because the debate was so frivolous. It's a reference to the book Gulliver's Travels by Jonathan Swift in which an island folk was split about from which end you should crack a boiled egg. (I'm a big endian for example).

Re: Inverting a binary tree using x64 assembly

#23

Post by tux3 »

cgh wrote: post #10

> I will be using x64 assembly with the AT&T syntax as it is objectively superior than the Intel syntax. This made me laugh because it must be a reference to this: https://news.ycombinator.com/item?id=33652023 > I contend that the AT&T syntax is harmful and bad, and should never be used, for any reason, under any circumstances, by anyone.

>I will be using x64 assembly with the AT&T syntax as it is objectively superior than the Intel syntax.

Them's fighting words.

Re: Inverting a binary tree using x64 assembly

#24

Post by efficax »

_8j50 wrote: post #11
cgh wrote: post #10

> I will be using x64 assembly with the AT&T syntax as it is objectively superior than the Intel syntax. This made me laugh because it must be a reference to this: https://news.ycombinator.com/item?id=33652023 > I contend that the AT&T syntax is harmful and bad, and should never be used, for any reason, under any circumstances, by anyone.

AT&T really is annoying but it feels like the big vs little endian debate. Fairly easy to convert between the two as well.

except now that everything depends on the internet, and words that go over networks are big endian, it seems insane to throw away millions and millions of cpu cycles every year converting them to little endian to be processed by our little endian cpus. sure, it's a single cpu instruction, but between every computer in the world, almost all of them being little endian arm or intel, that's billions and billions and billions of instructions wasted.

Re: Inverting a binary tree using x64 assembly

#26

Post by classified »

sedatk wrote: post #22
_8j50 wrote: post #11

Earlier quoted context omitted.

AT&T really is annoying but it feels like the big vs little endian debate. Fairly easy to convert between the two as well.

For those who don't know, that's why big and little endian were called that, because the debate was so frivolous. It's a reference to the book Gulliver's Travels by Jonathan Swift in which an island folk was split about from which end you should crack a boiled egg. (I'm a big endian for example).

I'm firmly in the little-endian camp for eggs, but big-endian for CPUs.

Re: Inverting a binary tree using x64 assembly

#27

Post by devit »

That solution is terrible, with a bad algorithm that requires O(tree_height) space (the optimal one involves temporarily using left/right pointers as a parent pointer so that you only need constant space) and lacking any sort of assembly optimization, being worse than what a compiler would produce (e.g. it's a real mystery how the author managed to decide that local_right should be spilled on the stack).

Definitely not what you want to submit to someone testing your programming skills.

Re: Inverting a binary tree using x64 assembly

#28

Post by adrian_b »

danbruc wrote: post #15

Assume RAX points to the root node and nodes just contain two child pointers and everything is aligned and whatever. :invert cmp rax, 0 jnz swap: ret :swap push rax mov rax, [rax] call invert mov rbx,[rsp] xchg rax, [rbx+8] mov [rbx], rax call invert pop rax ret The last time I used an assembler was before x86-64 was invented, I am not even sure I ever used one in protected mode. But that seems a totally reasonable w…

The variables on the stack are the most efficient after registers, so you are right that a local variable should be kept into a register if possible, otherwise in the stack, and only then in other places (e.g. if it is too large for the stack).

However, when writing in assembly one must pay attention that at least RBX, RBP and R12 through R15 must be preserved by any function (on Windows also RDI and RSI must be preserved).

So in your code you should not use RBX, but a volatile register, e.g. RDX or RCX. If you would insist on using RBX, it would have to be saved and restored.

Re: Inverting a binary tree using x64 assembly

#29

Post by fear91 »

_8j50 wrote: post #12
fear91 wrote: post #3

You can use the 32bit xor to reset the register. Also TEST REG,REG might be better for checking if it’s zero.

Is 32 bit cheaper? Still 1 cycle.

Yes, it’s 1 cycle but it’s longer to decode and occupies more of l1i cache. It’s not all about execution cycles.

Re: Inverting a binary tree using x64 assembly

#30

Post by scheme271 »

nixpulvis wrote: post #16
_8j50 wrote: post #12

Earlier quoted context omitted.

Is 32 bit cheaper? Still 1 cycle.

I was thinking of this from the perspective of CPU pipeline pressure, but in reality it seems prosessors are indeed smart enough to avoid burdoning the ALUs execution with these kinds of special cases. Read more here https://stackoverflow.com/questions/17981447/microarchitectu... > [...] these zeroing instructions extremely efficient, with a throughput of four zeroing instructons per clock cycle. Also, the xor instru…

The xor reg, reg is also special cased because it's a quick way for compilers to reinitialize a register and indicate that future uses of that register don't depend on any previous operations. It helps the cpu to parallelize any future instructions that use that register since the cpu knows that those instructions don't depend on anything that happens before the the xor.
Post reply on HN