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

61–70 of 73 posts

Re: Inverting a binary tree using x64 assembly

#61

Post by trelane »

pixel_tracing wrote: post #55

So anyone have good recommendations on learning assembly? I followed the link to the instructions ABI but can’t really read on my device.

For learning assembly, usually you learn the syntax for your assembler. The rest of it (the majority of it) is then learning what instructions are available on your platform.

I liked http://rayseyfarth.com/asm/ as an intro to both. I'd already had a class on computer architecture that did assembly before that, though.

Once you get going with that, you can download and read the Intel or AMD programmers manuals. Of course, this assumes x86_64.

Re: Inverting a binary tree using x64 assembly

#62

Post by teknas »

TheRealPomax wrote: post #18

This is pretty damn cool, but unfortunately you failed the interview as you accepted the challenge to use x86 assembler, but solved the problem using a different programming language from the one we asked you to use. We'll keep your resume on file, and if there are any openings in the future we encourage you to apply for those.

(I am the post author). I wrote the original version of this post using x86, but leetcode won't accept it. So I had to improvise...

Re: Inverting a binary tree using x64 assembly

#63

Post by chx »

nmilo wrote: post #60
sedatk wrote: post #22

Earlier quoted context omitted.

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

Genuinely curious, what are any advantages of big endian other than "it's how we write numbers in base 10?"

Signs and strings

Re: Inverting a binary tree using x64 assembly

#64

Post by LanceH »

tom_ wrote: post #44
aftbit wrote: post #42

What does it mean to "invert" a binary tree?

"Flip" or "mirror" is probably a better term. It seems the goal is to swap left and right: https://leetcode.com/problems/invert-binary-tree/

I don't get why this one is the meme. Just because it's recursion? Because it's (nearly) pointless? There are so many other algorithms I find more difficult/more tedious.

Re: Inverting a binary tree using x64 assembly

#65

Post by MobiusHorizons »

roperj wrote: post #57
adrian_b wrote: post #28

Earlier quoted context omitted.

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 pres…

> The variables on the stack are the most efficient after registers Why are variables on the stack more efficient than other memory accesses?

The top of the stack should generally be already present in the cache, so stack memory would be faster than heap memory where objects aren’t necessary as close together or accessed as frequently.

Re: Inverting a binary tree using x64 assembly

#66

Post by account42 »

monocasa wrote: post #36
classified wrote: post #26

Earlier quoted context omitted.

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

Watch as every pitchfork gets pointed at you when you talk about middle endian. Which is a real thing. There are systems that would store, say, a 32-bit word as two 16-bit words that were big endian relative to each other, but little endian within the 16-bit word.

Yes, but which order are the bits stored in each byte?

Re: Inverting a binary tree using x64 assembly

#68

Post by xgkickt »

roperj wrote: post #57
adrian_b wrote: post #28

Earlier quoted context omitted.

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 pres…

> The variables on the stack are the most efficient after registers Why are variables on the stack more efficient than other memory accesses?

Register renaming. Stack references are more likely to be in the register file.

Re: Inverting a binary tree using x64 assembly

#69

Post by menaerus »

roperj wrote: post #57
adrian_b wrote: post #28

Earlier quoted context omitted.

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 pres…

> The variables on the stack are the most efficient after registers Why are variables on the stack more efficient than other memory accesses?

I am not familiar with any other reason besides the fact that stack-pointer arithmetics are done through a dedicated HW, called stack-engine, which sits in the CPU frontend. This effectively means that stack-pointer uOps are going to be get executed quicker because they do not have to go all the way through the CPU backend processing. This also saves some of the bandwidth on the CPU backend side allowing other uOps to be processed sooner.

Re: Inverting a binary tree using x64 assembly

#70

Post by plasticchris »

LanceH wrote: post #64
tom_ wrote: post #44

Earlier quoted context omitted.

"Flip" or "mirror" is probably a better term. It seems the goal is to swap left and right: https://leetcode.com/problems/invert-binary-tree/

I don't get why this one is the meme. Just because it's recursion? Because it's (nearly) pointless? There are so many other algorithms I find more difficult/more tedious.

I think it’s a meme because the home brew author tweeted that he was rejected by Google for failing to invert a binary tree.
Post reply on HN