4 ms·

Yikes, what's my thesis from 1998 doing on HN? AMA, I guess. The idea was to make performance be a smooth function of policy parameters by adding randomization

by tlb 5y ago

Yikes, what's my thesis from 1998 doing on HN? AMA, I guess. The idea was to make performance be a smooth function of policy parameters by adding randomization. In many systems it's a jagged function and hard to optimize. For example: compilers have to make a choice whether to unroll loops. Unrolling generally uses fewer instructions, but also increases code bloat and therefore cache misses. Compilers have a policy with some tunable parameters to decide how much to unroll any given loop. Compiler writers tune those parameters by trying several to see what gives the fastest programs overall. The map from parameters => performance is very jagged, because sometimes increasing code size decreases caches misses because of associativity. If you look at the graph at the top of page 38, it shows cache miss rate as a function of code bloat. Slight changes in size cause large, unpredictable changes in performance. If you add some randomization here and there and take an average across many random seeds, you can get the nice smooth graph on page 45. Sadly, no compiler today does this. One reason is that people like reproducible, consistent builds. There's also an application to network congestion control. I think this one has become less relevant over time, because modern networks have background activity enough to avoid performance artifacts.

groby_b 5y ago
As a past victim of a compiler that used simulated annealing to optimize- you can get reproducible builds if you control the seed. It still becomes hell when you need to target an optimization to a specific spot. Or if the optimization is actually flawed. So, as much as I admire the thesis, I'm going to disagree on the "sadly" part :)
spenczar5 5y ago
This general idea of randomization is definitely in use. Randomized jitter is fairly common in exponential backoff algorithms for networked APIs. The jitter smooths out the waves of retries when a service goes down. Without it, the thundering herd all arrives at once and can keep the service from coming back up (because caches are cold, for example). This turns out to be really, really effective [0]! Separately, this thesis has a comment that "Lack of extreme sensitivity is fundamentally a desirable property of systems" which I think has been underappreciated. I worked on a team that used a lot of "circuit breakers" [1], which intentionally introduce a very sharp change in system behavior based on error rate: once you get too many errors from a backend, you stop sending it _any_ traffic until it responds consistently with non-errors. But this whiplash can cause as many problems as it solves - and the problems were much harder to understand. Anyway - it's too bad these ideas didn't catch on more broadly. They seem really useful. --- [0] https://aws.amazon.com/blogs/architecture/exponential-backoff-and-jitter/ https://aws.amazon.com/blogs/architecture/exponential-backof... [1] https://en.wikipedia.org/wiki/Circuit_breaker_design_pattern https://en.wikipedia.org/wiki/Circuit_breaker_design_pattern
- motohagiography 5y ago
  Around this same time (1998) backoff thresholds on dampening and other issues with BGP convergence were benefiting from another recent and conceptually related paper on how random_drop being configured on tcp ports prevented SYN flooding. Lately, we have ChaosMonkey and other random failure generators for uptime as well. The thesis has the underlying principle so well articulated though. Adding randomness to improve robustness is a really beautiful idea. What caught me is that you found the effect was a performance increase in the overall system as a result of the additonal entropy. Nassim Talib took it up later and made it famous, but it's a deep principle. I was wondering how generalized we could say if, that you have a process of any kind, which is subject to another random process that stresses it, and it evolves and adapts in response to the random stressors, and performs better as a result, could we find a general accelerating principle for a given system? As in, at a level of abstraction, is this the same principle at work as in a random neural net? (Edit: this was just posted to HN frontpage, which runs down this rabbit hole: https://www.quantamagazine.org/anil-seth-finds-consciousness-in-lifes-push-against-entropy-20210930/ https://www.quantamagazine.org/anil-seth-finds-consciousness... )

by tlb 5y ago

groby_b 5y ago

As a past victim of a compiler that used simulated annealing to optimize- you can get reproducible builds if you control the seed. It still becomes hell when you need to target an optimization to a specific spot. Or if the optimization is actually flawed. So, as much as I admire the thesis, I'm going to disagree on the "sadly" part :)

spenczar5 5y ago

This general idea of randomization is definitely in use. Randomized jitter is fairly common in exponential backoff algorithms for networked APIs. The jitter smooths out the waves of retries when a service goes down. Without it, the thundering herd all arrives at once and can keep the service from coming back up (because caches are cold, for example). This turns out to be really, really effective [0]! Separately, this thesis has a comment that "Lack of extreme sensitivity is fundamentally a desirable property of systems" which I think has been underappreciated. I worked on a team that used a lot of "circuit breakers" [1], which intentionally introduce a very sharp change in system behavior based on error rate: once you get too many errors from a backend, you stop sending it _any_ traffic until it responds consistently with non-errors. But this whiplash can cause as many problems as it solves - and the problems were much harder to understand. Anyway - it's too bad these ideas didn't catch on more broadly. They seem really useful. --- [0] https://aws.amazon.com/blogs/architecture/exponential-backoff-and-jitter/ https://aws.amazon.com/blogs/architecture/exponential-backof... [1] https://en.wikipedia.org/wiki/Circuit_breaker_design_pattern https://en.wikipedia.org/wiki/Circuit_breaker_design_pattern

motohagiography 5y ago
Around this same time (1998) backoff thresholds on dampening and other issues with BGP convergence were benefiting from another recent and conceptually related paper on how random_drop being configured on tcp ports prevented SYN flooding. Lately, we have ChaosMonkey and other random failure generators for uptime as well. The thesis has the underlying principle so well articulated though. Adding randomness to improve robustness is a really beautiful idea. What caught me is that you found the effect was a performance increase in the overall system as a result of the additonal entropy. Nassim Talib took it up later and made it famous, but it's a deep principle. I was wondering how generalized we could say if, that you have a process of any kind, which is subject to another random process that stresses it, and it evolves and adapts in response to the random stressors, and performs better as a result, could we find a general accelerating principle for a given system? As in, at a level of abstraction, is this the same principle at work as in a random neural net? (Edit: this was just posted to HN frontpage, which runs down this rabbit hole: https://www.quantamagazine.org/anil-seth-finds-consciousness-in-lifes-push-against-entropy-20210930/ https://www.quantamagazine.org/anil-seth-finds-consciousness... )