That said, I've been amazed what the top engineers in the field can design and implement getting things right the first time without additional effort. Simple, minimalist, high performance implementations that don't sacrifice much. There is a thin line between the beauty of those architectures and grab bag of pattern matching complex and unecessary optimizations.
No, it is premature when it is not necessary for the deployment (at some future point in time).
When I was developing for mobile phones (long before the iPhone), the decision of what to optimize when required some educated guesses where the phone market would be in 6 months, when the application is market-ready. (And: In the end, we did optimize a lot of code that did need no optimization 6 months later, but those optimizations made development work much, much more bearable.)
Yeah, spot on. What's really important is answering the question of what's necessary, that's really the key. Sometimes you do know that optimization will be necessary in the future even when it's not needed right now. If that's the case, the earlier you attack it, the better. But all of us (me included) tend to spend time on things we believe are necessary that turn out not to be.
> For these situations its like taking a loan for technical debt. In the future you may need 10x the resources to fix but in many environments that's acceptable
Definitely. There is the gamble that if you don't know for sure and you wait it might cost a lot more later. But I would go a lot further than that. The problem is that if you take the other route and optimize early on the wrong thing, it makes optimizing the right thing 100x more expensive in the future, not just 10x. It can be more expensive to optimize the wrong thing than it is to optimize the right thing late. This is because optimizations often require a different way to slice the code, to feed the limiting system with a different batch size, or to invert your high-level looping structure and swap the inner loop and outer loop.
If you've ever done image processing in Python, I always think of numpy vs PIL as a good example of slicing your batches a different way -- if you do it the easy way in PIL, you can write cool stuff in an hour, but your code might take 60 seconds to run on an image. PIL loops over pixels, and you put complex ops inside the loop. Numpy is opposite, you put the operations on the outside, and the loops on the inside (to allow the loops to be run as native compiled code). Numpy's harder to learn, the code is inside-out from PIL, it takes longer to write & debug, but something that takes PIL 60 seconds will take less than 1 second using numpy.
Most of my serious optimization efforts in C++ have ended up feeling very similar to the PIL vs numpy issue, and what happens is that it takes a ton of effort to optimize the right way because I have to invert my whole program's structure. When I've done that only to discover I didn't optimize the right thing, it's a huge mess to un-invert and re-invert the right way.
> I've been amazed what the top engineers in the field can design and implement getting things right the first time without additional effort. Simple, minimalist, high performance implementations that don't sacrifice much.
Same here, some people seem to hit the right balance with less effort. Sometimes it's experience and good guesses, but often (from what I've seen) it's because if you watch the best engineers work, they spend more time communicating up front to make sure they're doing what's really needed, and they spend more time checking their assumptions as they go, writing tests, profiling, and talking with their peers and their management about what they're doing. They're able to recognize quicker when they're spinning their wheels on problems they want to solve, and not problems that the team or product really truly needs solved.
An anecdote from a project I'm working on. I'm writing some LED control software for light shows and using GPIO pins on various embedded Linux boards (CHiP, Raspberry Pi, Orange Pi) to generate the SPIO-like serial signal I need.
My first draft, for Raspberry Pi 3, is a wonder of compact bit twiddling, doing all the necessary operations to write to GPIO memory in one compact function.
For the second platform, the Orange Pi Zero, I found a Python library for GPIO access that someone had already written, saw that the gpio operations were broken out into separate files and pulled those files into my project. My first thought: this will never be fast enough, and the O-Pi Zero is slower than the R-Pi 3. Luckily, I decided to try it first.
Now the the gory details of writing to memory are hidden in the library and the logic in my code to generate clock pulses and write bits is a lot more clear. I had to tune the code differently - the delays in my code to generate the correct clock pulse width are shorter now that there is function call overhead, but that was easy to sort out with a bit of trial-and-error with a logic analyzer.
Yes! Exactly. I'm almost always surprised. And it's really important to remember what benefits you get from the unoptimized code too.
Once I wrote a controller input system in a game engine, the code that monitors and reacts to all the buttons on an xbox controller, for example. I spent a whole bunch of time making sure that when I hit X, the reaction code would trigger with almost no overhead at all. It did fancy stuff like watch for combos and sequences, and game designers could author the control schemes, and I spent a lot of time making sure that actions cost no CPU time.
Then one day I profiled it carefully and found out that the bottleneck was something I'd forgotten to check for -- the case when no buttons were being used. The case that is happening during 99.5% of frames.
The loop to check if something needed to be done had a pretty bad memory access pattern than was missing cache most of the time. I thought it would be close to a no-op, but it wasn't. I had to refactor the whole thing and flip it inside out, and I realized I'd wasted a bunch of dev time fixing the code that reacts to one button at a time. It doesn't matter how slow a single action is, because it'll never show up in the profile. It does matter if I waste a few hundred thousand cycles traipsing through memory missing cache with every instruction.
It's a pretty short term optimization though.
Sure, it'll get you working, but working on a code base with no duplication means that once you find a bug and fix it, you don't need to hunt for duplicates to fix. It also means that if you're debugging something, you know exactly which code path was taken instead of "oh I thought it using X but it's using slightly different Y."
Whether that's a good trade off or not really depends on how long this code will be maintained. If it's front end glue code that will be tossed out when the CEO decides in nine months that the website should use X technology instead, then yeah, that's a fair trade off. Much less so if you know this code will be there 5-10 years down the line.
I would argue this always depends upon what you're doing. For example, in webdev, the culture of prototype fast and break things fast is very abundant, and makes sense when you're just trying to figure out if what you want done is even possible. However, there are many times where you /do/ have to consider the performance impact, because with it, what you're making isn't going to be nice to use.
By dogmatic, I think they meant individuals who will actually argue that '100ms' loop times are 'tiny' and shouldn't be a problem. They don't get the concept that its just one small part of your code, and the rest of it combined can make an entire process take up to 5-10 seconds to do something that should be in a blink or two. Learning about optimization is a part of learning programming, and knowing when to use it. The problem is when you don't know it, and fumble around trying to do so when you've got much bigger problems further ahead.
I ran into this problem a lot with image filtering and working with Canvas's to build an image editor. I talked with some communities about the Uint32Array implimentation in chrome and other browsers and how some of the ES6 goodies, like 'let', are actually bad practice when you start to get into image filtering, because just iterating over all the pixels in an image by using "for(let i=0;i< pixel.length;i++){}" is 3x slower than using var, causing just a single full loop to be 80-120ms on a good computer.
TypeScript compiles down to var, though, so its less of a problem there, but I met a lot of resistance in that statement in general, even though its true, because there's a lot of dogmatism in programming. At the end of the day I'd rather learn and teach good practices and not tell people they're pre-optimizing unless they really don't know much about what they're working with.
BTW, this is a really good example of why people like to avoid premature optimization.
Performance oriented code frequently has to break all the rules, it often goes against all "best practices" for code that isn't performance critical. If you do it too early, you will wreck your codebase's ability to deal with 1- non performance critical code and 2- other performance issues than the one you solved.
If you make it a rule to avoid using 'let' everywhere, then you lose the safety mechanism of block scope variables, something that a lot of people agree is a good idea.
It's very easy when you find out that let is 3x slower to stop using let, but then if you do that you're prematurely optimizing everything. And if you don't do it, everything you write is a little slower than it could be, and that will nag at you.
Functional programming is another good example of what many many people consider a good idea for code safety, and yet it is frequently abysmal for performance. Just to use another JavaScript example... using map() has historically been about 10x slower than using a for loop.
The singularly smartest engineer I know, who's now managing a huge team at NVIDIA, said to me that engineering for features is a solved problem, but engineering for performance is an unsolved problem. We know how to do class hierarchies and architecture and pub-sub systems to make a 10M LOC application manageable. We don't know how to write high performance code on that scale.
Which is why I said its bad practice in specific cases, currently. 2.5 Million iterations is a use case, not a general rule.
Programming is complicated, and as such you should know not to make the assumption that a use case isn't going to apply everywhere. Rather, you can say that microseconds of performance difference aren't a good reason to not use let, unless, you're not using something that compiles down to var, and you're going into the millions of iterations.
But, the point I was trying to make is that even when you talk about performance problems, devs jump the gun to 'pre-optimization', partially because they themselves don't know how well code performs, and partially because of misapplied dogmatism.
Wow, really? Any idea why? Seems odd when map() imposes fewer guarantees and can be implemented, in the worst case, with a for() loop...
This also depends on what you're comparing. Map always allocates a new array. In my Chrome 57 right now, map() is 4x slower than new array + a for loop of push().
But it's 100x faster to re-use an existing array... (a for loop of array element assignment)
This is good to know! I suspected, but never verified. I assume this will get fixed over time, since 'let' is brand new.
But JavaScript in general isn't well suited to image filtering, right? Certainly worth using, if at all possible, either CSS filtering or WebGL. Either of those will be much faster. Depending on what you're doing, some complex filtering operations will even be faster to upload to a back-end, process, and download the result. :P Is WebGL something you avoided because it won't work for you, or something you avoided because it's more costly development wise?
Hey overall, I agree with everything you say, and I'm still comfortable saying, dogmatically, never optimize prematurely. What that means to me is don't do engineering for problems you don't know you have. If you're not sure, then you don't know. If you're doing filtering, and napkin math proves in advance that you can't beat 5fps and your requirements call for 15 fps, then you do know.
In my mind this even fits with startups, because a startup's mission is to find the product and market, to figure out what's possible and then execute on it.
So ultimately I agree 100% it always depends on what you're doing, my additional caveat is always know what you're doing. :)
CSS only has basic filters, and WebGL is only possible for per-pixel manipulation, such as brightness or contrast. This is because WebGL is just shaders, and half of shaders are per-pixel, along with some other fun things you can use with multiple buffers, but you can't actually get /back/ the processed data even if you got all the pixels into a single loop. With WebGL 2, this may be different due to some new buffer types, but I don't think its made for it. Any time you do an algorithm that is dependent upon surrounding pixels, such as dithering, you're stuck with JS.
https://tools.czaux.com/space-pixels/
Here's an example of in-browser dithering to a fixed palette set that works pretty well, using RGBQuant modified with alpha support. The overall canvas uses FabricJS for manipulation.
Oh if you need the pixels back, you can certainly get them using glReadPixels(). It's a bit expensive in WebGL land, though it is much less expensive than looping over pixels using JS. And often there are ways to get around needing the pixels back, depending on what you're doing.
You can also do loads of non per-pixel tricks, including filters that need the surround, using multiple passes and clever shaders, you are not as limited with WebGL 1 as you think.
https://5013.es/toys/dithering/
https://www.shadertoy.com/view/MslGR8
This is what I'm talking about, you have to slice your program differently if you optimize it. Your high level structure and outermost loops will look different if you use WebGL instead of JS. And yes WebGL 2 is even better.
But, this is all much trickier than writing your straightforward loops in JS. That's the price you pay for performance, your architecture will be kinda crazy if you do it in WebGL, and it will not be easy to go back if you discover you optimized for the wrong thing.
I don't know what you're doing exactly, but when you do need dithering, it's usually the last thing you need to do before output, and it's usually less important that the dither is fast than most other operations you need in an image editor.
BTW, random order is lower quality, and error diffusion is better, only for for very low res color palettes. If your result is more than 256 colors, it's irrelevant, and for high quality dithering, e.g., 16 bits per channel colors to 8 bits per channel for print, random ordered dithering is superior.
https://community.arm.com/graphics/b/blog/posts/when-paralle...
http://www.cs.cmu.edu/~imisra/projects/dithering/HybridDithe...
https://www.shadertoy.com/view/4dt3W7
That last one is ugly, but it's a great proof of concept here. You could get error diffusion in a shader using 2 passes. The first pass you render to texture, and the second pass, you can sample the texture however you want. Note how in this example, the error diffusion propagates backwards from what you would normally do in JS or C++, because it's a shader looping over destination pixels, not code that loops over source pixels.
> In WebGL, you can read the pixels of the image, but you cannot modify and read.
I don't know exactly what you mean here. You can modify & read pixels using render to texture, or using multiple passes.
Render to texture will be faster, if you can do it. Multiple round-trips from CPU to GPU and back will be slower, so you want to limit the number of trips, but it's easy to do.
Dithering requires quantization. If you mean things like brightness and contrast, yes, webgl is better for that. But quantization with error diffusion dithering is still based upon previous modified pixels, so you cannot just send a bunch of pixel info to webgl, you have to do each pixel seperately. Meaning, pushing through 2.5Million seperate inputs sequentially, and having to use glReadPixels() 2.5Million times.
>BTW, random order is lower quality, and error diffusion is better, only for for very low res color palettes.
Not in any of the images I have used. Ordered dithering looks fake, because it appears like a texture to the image. Dithering with error diffusion kernels, like Floyd-Steinberg create a less obvious texturization that still preserves the underlying image.
>https://www.shadertoy.com/view/4dt3W7
From what I'm reading, for every pixel, it is processing a 250 iteration loop that gets the pixels in the row and builds errors based upon those. However, it is not modifying any pixels as it goes, this is a parallel operation independent of each other. Good error diffusion with a kernel requires previous pixels to be modified, and errors to be built upon them, which is why it is a sequential operation. I don't see any destination-dependant pixel manipulation.
>Multiple round-trips from CPU to GPU and back will be slower, so you want to limit the number of trips, but it's easy to do.
If its possible to get data back from Uniform Buffer Objects in WebGL2, it may be possible to send up to 1000 or so uniform pixel values, but that is the general cap. Some GPU's have less. Unless I am missing some magic buffer you can use to write out many pixels too, and in that case I would be very interested in testing that, but shaders are designed to output a single pixel per instance.
>https://community.arm.com/graphics/b/blog/posts/when-paralle...
From what I'm reading, this is using OpenCL, and parrallelizing in rows, but these rows have height. A single thread processes one row and sequentially goes through the pixels like normal error diffusion. Just that this breaks different parts of the image up. I may have to try this out in JS and see if perhaps it can thread better that way. ty.
Why do you think that? You certainly can get previously modified pixels, you can send millions of pixels to WebGL with a single call (as a texture). Nobody calls glReadPixels millions of times, that's a bad idea. :) You might want to investigate multipass rendering techniques. Small kernel convolutions, for example, are standard and simple operations in WebGL. People use blur & edge filters all the time, and those depend on neighborhood computation.
Regarding the 1-d error diffusion shader on shadertoy, it is using a gather instead of a scatter. It's a pull instead of a push, he flipped the operation inside-out. It is still computing error diffusion correctly (but for only a single pixel row). And it's running at 60fps.
This is the whole point I tried to make above multiple times wrt performance: this code looks unrecognizable compared to the straightforward CPU serial way to implement error diffusion.
The reason this example is correct (in 1D) is because it recomputes the error propagation for every destination pixel; it's wasting almost all of the computation it's doing because in this case it's not sharing the error computation. But that doesn't mean it can't -- this is just a proof of concept on ShaderToy, not the limit of what you can do. You can't do multipass with ShaderToy, and multipass is how you share pixel results from one iteration to the next.
> Unless I am missing some magic buffer you can use to write out many pixels to
It sounds like you're missing render to texture and multipass techniques, the ways to use textures as compute I/O. To do multipass in WebGL and share the results of computation from one pass to the next, you create an offscreen framebuffer for your results, and you render directly to that framebuffer. You can then use the result as an input texture for the next pass (via glCopyTexImage2D) or you can read back the buffer (via glReadPixels) and then you repeat. Using glCopyTexImage2D is much faster because you never leave the GPU.
I think you could do error diffusion by rendering the error to a texture, and using a multipass technique that only needs as many iterations as the maximum distance any error could travel. In the worst case it'd probably be the greater of your image width or image height, e.g. 512 passes for a 512x512 image, but in practice I think you'd be done much sooner. That's assuming there isn't something hierarchical and more clever that could do it in log(width) passes, which I suspect there is.
How are you writing many pixels to a framebuffer in a single instance? frag_color returns one pixel. Even if that OpenCL implimentation works in webgl, you'd still be at only 8 threads, so only 8 pixels that can be done at the same time, then you have to pass in the output to process again. 259200 glCopyTexImage2D calls for a 1920x1080 image since its 2073600 pixels.
I'll definetely look into this more, since that openCL implimentation might hold some answers on how the error distance is seperated to allow for 8 rows at a time.
Whoa, hang on. Hey I only mean this to be helpful not insulting, but it sounds to me like you may have some misconceptions about the way WebGL works. I know how easily that can be taken the wrong way, especially in text, so again I apologize in advance and I don't mean that to be rude at all. It would be best to back up and understand WebGL.
If you're doing image processing in WebGL, then to write many pixels to a framebuffer all at once, you draw a single polygon that covers the entire viewport. Your shader is applied in parallel to all pixels drawn. That is how ShaderToy works, it renders a single quad to the viewport and applies whatever shader you give it, the GPU runs that shader on all pixels rendered.
There are never hundreds of thousands of buffer read calls, you only need a handful. For a blur, you only have to do a buffer read once, and your shader samples the 3x3 neighbor pixels.
You don't need OpenCL, that's a level of complication you don't need. I may have given the wrong impression with that link.
Check out this image processing tutorial using basic WebGL 1, and pay attention to how it works:
https://webglfundamentals.org/webgl/lessons/webgl-image-proc...
Here is the demo from that article that uses the techniques I've been talking about. All of the filters in this demo are doing neighborhood computations. And note you can apply multiple filters. There is no texture copy here, this tutorial renders directly to a texture in one pass, and then samples that texture in the next pass and so on. The iterations or feedback that you're looking for happen by combining render-to-texture with drawing the viewport polygon multiple times.
https://webglfundamentals.org/webgl/webgl-2d-image-processin...
>Whoa, hang on. Hey I only mean this to be helpful not insulting, but it sounds to me like you may have some misconceptions about the way WebGL works.
You draw a simple quad, which the shader then processes all the pixels in parallel, returning their frag_color as the output color. It can read textures and other source information, but it does not have access to what is being processed currently for other pixels, because its parallel. You have to wait until it has rendered that, and then pass it in again. I am unsure what I am misunderstanding.
>https://webglfundamentals.org/webgl/lessons/webgl-image-proc...
This was a cool insight into using framebuffers for multiple passes, thank you.
>Here is the demo from that article that uses the techniques I've been talking about. All of the filters in this demo are doing neighborhood computations. And note you can apply multiple filters. There is no texture copy here, this tutorial renders directly to a texture in one pass, and then samples that texture in the next pass and so on. The iterations or feedback that you're looking for happen by combining render-to-texture with drawing the viewport polygon multiple times.
From what I'm seeing, this is not just a couple passes, its a pass per-filter. None of the filters singularly rely upon multiple passes, their output is calculated purely on the image that was filtered before it, meaning the filter itself doesn't need to write pixels and then read them again. You can see that in the for loop that calls setFramebuffer() and drawKernel(). I understand that you can apply a shader, and put its output back in, but I still fail to see how you're avoiding doing that at the very least in the hundreds of thousands of times. error diffusion dithering classically is sequential from top to bottom, or bottom to top depending upon serpentine or not, I don't think you can just process a ton of pixels at the same time and still look anything like a sequentially done Floyd-Steinberg.
You're right; this demo is 1 pass per filter type. None of them require multipass, but the entire demo is multipass. There could be a filter that needed more than 1 pass, but in this case there isn't.
1 pass means: render all pixels in the viewport, and run the shader on all pixels rendered. You've got that part. The trick is you get to access a texture, and the texture is the result of the previous pass. Furthermore, inside the shader, you can address and access any pixels from the previous pass, and you can access multiple pixels from the previous pass to render one destination pixel.
I think the millions of reads you're looking for are the texture() calls happening inside the shader. The [render / render-to-texture / copy pixels / copy texture image] calls process all pixels in the viewport in a single call. The shader applies to all pixels, but a shader only gets to touch any given destination pixel once per render. But the shader can read as many source pixels as it wants.
Because the shaders aren't limited on their reads, but they are limited on their writes, you have to re-organize your algorithm accordingly. You keep reiterating that error diffusion is spreading out from top to bottom, and I keep re-iterating that it has to work differently in WebGL, we've been talking past each other a little bit here.
You're right; you can't spread things out (scatter) using WebGL during a single pass, you can't do the classic Floyd Steinberg implementation the same way you do on the CPU. So it's important to understand that there is another way to do it, and it doesn't look like what you're used to. It doesn't spread things out by pushing error around inside the loop. It spreads things out by letting each destination pixel pull the error from it's neighbors before computing it's own error, rather than pushing it's own error to it's neighbors after computing. This is known as a gather, as opposed to scatter. It is mathematically the same thing, but the order of operations is turned around.
Here's a diffusion demo, it's reaction diffusion, not error diffusion, but ultimately exactly the same diffusion process. Each pass diffuses the previous pass by 1 step.
That makes significantly more sense now. I thought you were saying I could do normal floyd-steinberg sequentially somehow.
I am unsure on the mathematical implimentation, but I will keep looking at this. I would think there would be a paper on this method somewhere.
I really appreciate the time you've taken to respond. Not many webgl people out there that can actually point out how it all works and whats possible, and I definitely learned something.
That is an implementation detail. Of specific chrome versions.
That does not make let itself bad practice. In principle it should be significantly easier to optimize for a compiler because its more limited scope. So in the long run or possibly on other browsers it is likely best practice.
Putting transients before long-term behavior leads to urban programming myths and legacy baggage.
In fact in some jsperf benchmarks on chromium let happens to be faster for me.
Not when the problems still exist. When they stop existing, sure, but the statement generally goes along with how some parts of ES6 are not well optimized yet. Over time, they should be optimized, but I cannot design something for an event that hasn't happened yet and cannot be tested.
let is better than var (in every way), so you should never ever use var. Of course you can design for the future. Designing for the future is using let and transpile to a dialect that is used by most browsers today.
Not in the case I presented. let has benefits, but that does not mean its 'better in every way'. Again, dogmatism. Granted, the case I give is many, many iterations, it still is a problem if you're doing image filtering.
And FWIW, of all the problems that matter to me and my teams, I find premature optimization to be far, far more wasteful of money and human energy than wasted CPU cycles. There are definitely times to worry about performance, and I fancy myself a deeply performance oriented person, and yet I am and will continue to be proud of my dogmatic adherence to avoiding premature optimization, because in my experience it's not a myth at all. I have watched literally years and millions of dollars wasted multiple times by teams that decided to prematurely engineer high performance solutions to problem they thought they had but didn't actually. So I'm way more scared of premature optimization than I am of wasting cycles.