To anyone interested in learning more about Shannon entropy, I recommend reading Shannon's original article. It's highly readable!
There's a link to the PDF on https://en.m.wikipedia.org/wiki/A_Mathematical_Theory_of_Com... .
Measuring Information in Millibytes
11–19 of 19 posts
Re: Measuring Information in Millibytes
#12> You decide to try running with optimizations 1-128 enabled, and 129-256 disabled. That run fails. Now you know that one of the first 128 optimizations is to blame. You try again with 1-64 enabled, and 65-128 disabled, and that run passes. The bad optimization must be between 65 and 128. Continuing in this fashion—a binary search—you're able to locate the faulty optimization in just eight steps. This doesn't work fo…
I think for pairs you can still do a logarithmic search, it’s just not base 2.
A trinary or quaternary search should be able to find two bugs at once (and intuition tells me a quad search should be able to handle three).
Say you have 16 optimizations and 7 and 12 don’t work together. Eliminate the first half, the second half, the odd or the even opts and the build is still green. But if you remove the first third or quarter the tests still fail.
So in a trinary search you might see 1-16 -> 6-16 -> 6-13 -> 6-8,12-13 -> 6,7,8,12 -> 6,7,12 -> 7,12. Including the first and last sanity checks you’re in for about 8-14 test passes for 16 tests, which is a lot better than 2^16.
But there’s still a binary search you can do, and that’s a bisect of the commit history. Before some commit this bug didn’t happen. And that’s going to contain one half of the bug. Now you run a second binary search to find its complement.
Re: Measuring Information in Millibytes
#13> This is a little more than eight thousandths of one bit. Therefore, the information given by one passing test run is just a little over one millibyte. To debug this compiler, we're going to be running hundreds and hundreds of experiments, each of which gives us a tiny fraction of one bit, until we can finally put together the single byte we need to isolate the faulty optimization. It doesn't work that way. If you'r…
In the limit of infinite passing tests, do we recover the byte we sought? Or does it asymptote to some other quantity? I'm asking relative to a maximum entropy prior.
Re: Measuring Information in Millibytes
#14Another example of sub-bit information:
Base85! 85 different ASCII characters have lb(85) ≈ 6.4094 bit. With 5 of then you get slightly more than 32 bits. Each of the 5 characters have a surplus 0.4 bit of information to add up to 2 bits.
To encode to Base85 use a 32 bit entity as an 32 bit unsigned integer then divide by 85 five times and take the remainders (from 0 to 84) as indices to the string of all Base85 characters of length 85.
To decode view the characters as a number written in base 85. This means that there are a few Base85 representations which are more than 2^31 - 1, this would mean an decoding error.
Re: Measuring Information in Millibytes
#15Tarsnap storage costs 0.25 picodollars per millibyte-month of storage.
And it works great! Well worth my picodollars.
I'm a fan as well, but I'm a bit worried about how slow retrieving an archive is. any suggestions for increasing the speed of that? the only solution I've thought of is to split up my archives into smaller pieces.
Re: Measuring Information in Millibytes
#16Password entropy is another place where fractional bits can be encountered.
Re: Measuring Information in Millibytes
#17> You decide to try running with optimizations 1-128 enabled, and 129-256 disabled. That run fails. Now you know that one of the first 128 optimizations is to blame. You try again with 1-64 enabled, and 65-128 disabled, and that run passes. The bad optimization must be between 65 and 128. Continuing in this fashion—a binary search—you're able to locate the faulty optimization in just eight steps. This doesn't work fo…
Optimization fuel[1] is a neat solution: have the compiler perform only the first n optimization operations, then use binary search to find which operation was bad. You can then break execution at that point to see what is going wrong.
[1] http://blog.ezyang.com/2011/06/debugging-compilers-with-opti...
Re: Measuring Information in Millibytes
#18> This is a little more than eight thousandths of one bit. Therefore, the information given by one passing test run is just a little over one millibyte. To debug this compiler, we're going to be running hundreds and hundreds of experiments, each of which gives us a tiny fraction of one bit, until we can finally put together the single byte we need to isolate the faulty optimization. It doesn't work that way. If you'r…
I run into this with much larger p and have to explain it to coworkers.
Flip the scenario around: the code is fine but the test has a concurrency bug in it. It fails about 20% of the time. You ask someone to fix it. After six green test runs they declare the bug fixed. But then build 8 fails and so does build 10.
Why? Because probabilities aren’t additive, they’re multiplicative. You didn’t test 6p > 1, you tested (1 - o)^6 which will never be true.
In this case there was a 26% chance the test was still broken after 6 green tests. You need 11 runs just to get the probability into single digits.
(Another consequence of this is that if you have 5 flaky tests the probability of a green build is one in four, and the likelihood of getting multiple consecutive red builds is high enough that it happens every week or two).