Simple Code, High Performance [video]

https://www.youtube.com/watch?v=Ge3aKEmZcqY

by archagon • 5 years ago

141 82 5 years ago

youtube.com

jgwil2• 5 years ago

So does he have a special reversed image printed on his shirt just for this lecture format?

isaacimagine• 5 years ago

I looked into this a while back, yep.

devnull32• 5 years ago

This was good. I like the presentation.

---------

This can be a good interview question for Google to screw people over.

I was asked to write a code to generate maze (100x100) with the constraints that it should neither be easy not it should be hard. This was for L6 position.

omegalulw• 5 years ago

That's a very interesting. I am curious to hear what your answer was :D

Here's my thoughts on what a solution would need:

1. At least one path from source to target.

2. Some quantification of hardness. No of steps in optimal path? Number of turns in optimal path? Number of paths? Some weighted combination of all three?

Some preliminaries:

Finding optimal path, and finding number of paths can both be down in O(N^2) using DP. Finding number of turns is then trivial.

Now the Algos for 1:

Algo for 1: Naive backtracking, i.e., randomly generate paths until there are no paths. Evaluate each maze using the heuristic and output best one. Run for some fixed time t. This is exp time.

Another algo for 1. Generate a path as following: select K points on the grid, with the start and end being the first and last; then finding optimal paths in sequence (notice that this guarantees not cyclical path). Next, generate fresh path on an empty grid and overlay on the previous path. Keep repeating for some M paths. Now fill in non path pixels. Pick the best grid among these M steps. This is O(M*N^2).

Last Algo for 1: Throw the grid into an ILP solver and optimize the heuristic (exp time).

devnull32• 5 years ago

Well, I addressed the "neither easy nor hard part" upfront. My take was there has to be a solution and that too 1 solution. In other words, it had to be fair.

Second was the degree of false paths (term I made-up). This essentially governs the branching of each false path. Higher the degree higher the branching and higher the backtracking. This would make the maze harder.

So my algo was

1. To generate a valid path from top-left to bottom-right. (this is simple bfs/dfs walk). This is illustrated as path 1-2-3-4-5-6-7..-10 below. This ensures we have a fair maze.

2. Now from each number below, generate path in an outward manner till it hits walls. These are false paths. The "degree" mentioned above will dictate if there are further branching out of these paths.

1 * * * * *

2 3 * * * *

* 4 5 6 * *

* * * 7 * *

* * * 8 9 10

In the step #1 we note the row,col in a dict/hashmap. We use these in step #2 to ensure the dfs walk dont step on these row,col.

This is all I could conjure-up in 45 min including a code in python. I was labelled lean-no hire.

Edit: fixed the rendering of the maze

anandoza• 5 years ago

3 hour video with no timestamps, a minimal description, and comments turned off?

tigerwash• 5 years ago

Yeah, thought so too.

At least adding some major timestamps in the description would be great.

Attummm2• 5 years ago

I think many saw it already. He is great a programmer, his analysis on the initial problem and on his situation with Microsoft is on point.

aetherspawn• 5 years ago

"Simple code" -> very difficult to decipher use of SIMD intrinsics. Yikes.

He may have deleted 1000 lines of code, but he'll need a 2 hour inline video (with a 1000 line transcript) to explain how it works.

dralley• 5 years ago

Even if he had stopped before hand-rolling the SIMD, it'd still be a multiple order of magnitude improvement.

I do think it would have been useful to demonstrate that before going straight to hard mode.

werner18862• 5 years ago

He measures code 'simplicity' by how much work it makes CPU do, and not some made up metric like 'readability'.

philosopher1234• 5 years ago

How exactly is readability made up?

archagon3• 5 years ago

I really like this lecture format. What is he drawing on?

gary_0• 5 years ago

I guess he filmed through a pane of glass, and then flipped the video? It's trippy that he's physically writing backwards, but the text we see isn't reversed.

archagon3• 5 years ago

We see the whiteboard text scrolling sometimes, though.

throwuxiytayq• 5 years ago

I'd like to point out that this also means that his t-shirt has the logo pre-flipped. What an absolute madlad.

generichuman2• 5 years ago

He uses a lightboard [0] and flips the video.

[0] https://www.lightboard.info/

cryo• 5 years ago

I love these videos, it's the kind of no BS programming to press performance on modern computers. Also recommend the Handmade Hero series of him.

We have computers which are ridiculous fast, but tend to write code which is freaking slow. It's sad that most programs could be 100x faster.

nuerow4• 5 years ago

We have computers which are ridiculous fast, but tend to write code which is freaking slow. It's sad that most programs could be 100x faster.

I feel this sort of comment misses the whole point of going with code which is patently slower than alternatives.

The main reason is that performance is a constraint but not a goal, and once it is good enough then there is absolutely nothing to be gained by wasting time on seeking performance gains.

Meanwhile, the main resource in software development is man*hours. The faster you write software (add features, fix bugs, etc) the cheaper it is. Thus, software projects benefit the most by adopting and using technology which favour turnaround time, which means higher-level languages, generic full-featured frameworks, and code reuse. They are slow and bloated and not optimized, and they are used without optimization in mind. But they work and they work acceptably.

Your client and project manager does not care if you go with a O(n2) implementation that you can whip out right now by reusing a package and has acceptable performance even if there is a O(n) alternative that requires you a few weeks to implement and forces you to test, debug, and maintain a lower level implementation.

Performance is meaningless once it's good enough. It matters nothing if your browser wastes 1GB of RAM even though it could just use 100MB because practically everyone already has 8GB to begin with, and if would be foolish to waste resources prioritizing that if no one is willing to pay for that improvement. It matters nothing if your server has a relatively low throughput because it is wasting 10s of milliseconds doing nothing in each response if all your servers barely break 50% utilization. It matters nothing if your frontend is wasting 10s of milliseconds rendering a page if end users don't even notice any delay. If performance is good enough, work is focused on where it matters.

We know it's possible to get formula1-level performance by using formula1-level of engineering and maintenance, but the world runs on Volkswagen hatchbacks.

yakubin• 5 years ago

In my experience, people waste performance and manhours at the same time. Many abstractions create more code instead of reducing it, at the same time making the code slower, harder to read and maintain. Would you rather maintain a couple hundred lines of straightforward code or thousands of lines of class hierarchies with delegates and whatnot?

See John Carmack on Inlined Code: <http://number-none.com/blow/blog/programming/2014/09/26/carm...>

anikki• 5 years ago

“Good enough” is defined by the inability of stakeholders to conceive of transitive benefits. Compute performance suffers the tragedy of the commons.

bsenftner• 5 years ago

All this sounds good and practical, until an organization operating in your market optimizes their technology requirements. Suddenly that organization has both exponentially faster technology support for everything they do, and their expense in doing so is exponentially less than your organization. Optimized technology is not "good enough", it changes the nature of the conflict to revenues.

Chris_Newton3• 5 years ago

Meanwhile, the main resource in software development is manhours. The faster you write software (add features, fix bugs, etc) the cheaper it is.*

People have argued that developer time is the most precious resource since forever. In more recent times, people have also argued that pushing new features needs to happen as quickly as possible, particularly in the context of web and mobile apps.

I am rather sceptical about both claims.

Yes, developer time is important. Developer compensation is probably the largest single cost in most software development organisations and you want a good return on that investment.

Yes, the goal is acceptable performance rather than perfect optimality every time. The best is often the enemy of the good here.

And yes, that means it is foolish to invest weeks of developer time to implement an O(n) algorithm when you had an O(n²) algorithm that ran fast enough in practice.

However, what if you have a data processing job running on some cloud infrastructure that is charged according to usage, and carelessly using an O(n²) algorithm when you could have spent an extra day to write an O(n log n) one increased your AWS bill for that system by a factor of 10?

Performance can be important in other areas that sometimes get overlooked, too. In communities like HN, most of us probably enjoy the use of modern devices with relatively high specifications, but not everyone is so lucky. A classic “works for me” problem is developers running on high-spec equipment who don’t experience frustrations that their users with more modest equipment will run into, when maybe that “acceptable performance” shouldn’t be considered so acceptable after all.

And what about other types of software, such as embedded systems, where there are often tighter resource constraints and being able to use less powerful hardware components can have a significant impact on the overall cost to produce a device?

Meanwhile, I see little evidence that the relentless push to push changes around every five minutes is an automatic win. Yes, deploying changes like security updates and critical bug fixes quickly is important, but are users really happier — or, from a business perspective, willing to pay more for our software — because of the modern culture of continuous deployment and frequent updates of everything? That’s less clear.

It is undeniable that a lot of customers will still pay for poor quality software, which means shipping poor quality software can be an attractive and lucrative business model, which means paying lots of money to developers who will only produce poor quality software can work, which reduces the incentives for developers to do better. This is unfortunately the world we live in. But it doesn’t mean some of us running software businesses or working in software development can’t try!

SkeuomorphicBee• 5 years ago

This has been the prevailing mentality in the industry for a long time, being essentially a business dogma in IT since the 90s (for a good reasons, as you explained). I think Java is the personification of this concept (more specifically idiomatic corporate Java from the 00s).

But there is a recent small change of winds, where management is realising that being faster than the competition can have some business merit, being worth spending some man*hours. The lecturer explains it well in the beginning of the lecture. It is not a 180° turn, performance is not the priority (as it shouldn't be), but a relevance "differentiator". That is one of the drivers of the recent growth in compiled languages (Rust, Go, ...), Not the only one but it helped.

robalni2• 5 years ago

Performance is meaningless once it's good enough.

There is no level of performance that is "good enough". One person's "good enough" is another person's "pain to use" and it's someone else's "I can't buy that computer that I would like because it will not run this software well". Faster software means more options for the consumer, less energy usage and it will be easier to make computers because they don't have to be crazy fast.

I have a computer that is not one of the fastest in the world. I love this computer. It's tiny, beautiful and silent (no fans). When using this computer I can clearly see how slow a lot of software is. It's not the computer that is slow because it's definitely possible to write software that runs really fast on this computer.

One thing that programmers can do to make the situation better is to underclock your CPU when testing your software. On Linux this is very easy; just write the value "800000" to the files that match "/sys/bus/cpu/devices/cpu*/cpufreq/scaling_max_freq". Now your CPU will run no faster than 800Mhz. This will help you to notice when your program gets slow much earlier. And if you then think the performance is "good enough", it's very likely that your users will think so too because most people have a CPU that runs faster than 800MHz.

franknine• 5 years ago

I think it's just a matter of different industries having different situations.In game industry performance is a real business advantage thus it’s a goal. On consoles, every game developer works on the same machine, the one who can get the most computation out of the box can cram more visual effects or more complex AI behaviour into the game and win the race. (I know not all developers are into this photorealistic madness, but some big studios are still fighting over it) Even if you are working on mobile games, better performance means less battery drain (longer player engagement), less overheating, and being able to deploy onto older or weaker devices. (The performance scaling characteristic of the new Doom is so good that it can run on Switch) Again, these are real business values.

On the other hand, premium games generally generate little to none revenue after release. The gameplay and hardware would likely be different for the next title. For instance the rendering architecture changed from forward, deferred, to cluster in response to new hardware capabilities. Which means the maintainability and reusability of the game codebase is less important compared to other software projects. Also there is a tendency that game programmers receive less compensation compare to other industries (Higher supply of junior devs), so the calculation of man * hours would be different as well.

andrepd• 5 years ago

once it is good enough then there is absolutely nothing to be gained by wasting time on seeking performance gains.

Energy consumption, loading time, performance for anyone who does not have the latest computer/phone + fast and reliable internet.

In fact, every dev coding a user-facing application on a kitted-out laptop should be forced to test it with the shittiest machine + internet connection their users might have (or, say, 10% percentile or something). Sometimes it feels people live in a bubble where they assume the latest processors, 32GB of RAM, and stable 100Mbps+ internet is available everywhere.

It matters nothing if your browser wastes 1GB of RAM even though it could just use 100MB because practically everyone already has 8GB to begin with

Yep, a bubble indeed x)

superjan• 5 years ago

So this guy has had a t-shirt printed with a mirrored logo just to be able to use it with the transparent whiteboard.

Zababa10• 5 years ago

I wonder how much performance is gained by having the code written by just one person. At work we have a reasonably large (16 MLOC) codebase. At this point I don't think it's possible for one person to do everything, especially while adding new features. So what we do is that we create relatively clean interfaces, and have people code mostly inside those interfaces. But every time we go through one of those interfaces, there's a performance hit.

kjksf2• 5 years ago

In this case: nothing.

The fast renderer was written by one person in a few days. It's clearly a "few thousand loc" codebase, not "millions loc".

The 100x slower renderer was also written by one person (or at most few).

It really is the difference between programmers.

It's also a good example that 10x programmers do exist, at least in certain situations.

The Microsoft programmers are not dumb. They certainly are not cheap.

And yet here we have one guy who can write code that is 10-100x faster, in just few days.

Zababa10• 5 years ago

I don't think that's exactly true. It's not the same thing to write a piece of code as part of a whole system, vs rewriting that piece of code as an isolated part.

The 100x slower renderer was also written by one person (or at most few).

The difference between one person and a few is massive in my experience.

It really is the difference between programmers.
It's also a good example that 10x programmers do exist, at least in certain situations.
The Microsoft programmers are not dumb. They certainly are not cheap.
And yet here we have one guy who can write code that is 10-100x faster, in just few days.

I think it's a difference between incentives too. Microsoft programmers are not here to optimize for performance, but to push features, performance being one of them in some cases. For example, the research in file explorer is still painfully slow, probably because they have some other things to do. Many people could make it faster in a few days I guess. But these people aren't inside Microsoft being pressured to do other things.

Software made to demonstrate how fast something can be is made in a very different environement and with very different incentives compared to almost all comercial software. For pretty much anything out there, someone can take it, isolate it and make it run 10-100x times faster I think. The thing is, in most organizations you don't have that kind of time.

vashishthak2• 5 years ago

That's exactly how i managed to enhance the performance of my site. https://vashishthakapoor.com/ Keeping the features along with performance is a big challenge. Video is really explainatory to fix performance issues.

VHRanger• 5 years ago

Wow, your site is indeed fast. Good job!

vashishthak2• 5 years ago

Thank you so much mate. Means a lot. :)

Simple Code, High Performance [video]

Related Stories