Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Measuring Information in Millibytes

engineering.vena.io

Post reply on HN
Print view View original

1–10 of 19 posts

Re: Measuring Information in Millibytes

#6

Post by lucio »

>Why eight steps? Well, to differentiate between 256 equally likely possibilities requires eight bits. Each experiment, since it differentiates between two equally likely outcomes (pass and fail), provides one bit of information. Therefore, we need eight such experiments to give us the eight bits we need to determine the faulty optimization.

Is this explanation a little odd?

Each step in a binary search halves the amount of suspects, you need 8 steps because with 8 steps you go from 256 suspects to one.

I can't see it the way the article describes it.

It's just me? Anyone else found the article reasoning for 8 steps a little odd?

Re: Measuring Information in Millibytes

#7

Post by nayuki »

Data compression is another place where measuring in millibytes is feasible. For example, if a video codec took in pixels in RGB8.8.8 format (3 bytes per pixel) and has a 100:1 compression ratio, then you could say that the compressed video uses an average of 30 millibytes per pixel.

Re: Measuring Information in Millibytes

#8

Post by winceschwab »

lucio wrote: post #6

>Why eight steps? Well, to differentiate between 256 equally likely possibilities requires eight bits. Each experiment, since it differentiates between two equally likely outcomes (pass and fail), provides one bit of information. Therefore, we need eight such experiments to give us the eight bits we need to determine the faulty optimization. Is this explanation a little odd? Each step in a binary search halves the am…

Yeah, I noticed that too. Treating a byte as eight tally marks misses the point about the combinatorialnature of place settings.

It's not 100% wrong, because bit shifting and bit packing are real-world applications used in memory all the time.

But these are not the only possible values:

  00000001
  00000010
  00000100
  00001000
  00010000
  00100000
  01000000
  10000000
It's not incorrect to make a decision to limit one's input to those values, but it is incorrect to presume that binary data can only be recorded that way.

Treating those 8 place settings as eight lightbulb circuits that each need an individual test isn't the right mindset for someone performing compiler optimization.

Re: Measuring Information in Millibytes

#9

Post by infinity0 »

> 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 for the case where the failure(s) might be caused by a combination of a subset of the optimisations. That is,

1000 0100 0010 0001

all succeed, but

0101

fails.

A binary search is not possible for these more complex bugs. We had such cases in the reproducible builds project.

For the case where you can assume (subset A exhibits a failure => any superset of A exhibits a failure), then you can just go through all the options (in the OP's case 256) and switch them on, one at a time. Then the running time is 256, not 8.

For more complex cases where you can't assume even that, then you're stuck indeed with 2^256 test cases.

Re: Measuring Information in Millibytes

#10

Post by eridius »

> 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're dead set on measuring a single passing test run as a milllibyte's worth of information, you have to realize that every subsequent passing test run is worth less and less. Otherwise running a thousand passing tests would give you a full byte of information, and yet a thousand passing tests does not give you 100% confidence that the enabled optimizations are not buggy. The only way to get a full byte's worth of information is to actually hit upon a failing test run.

And in fact even this is mistaken. You don't have a millibyte's worth of information. You have a lot more. The number of passing test runs at a given optimization gives you a probability that the optimization is buggy. Claiming that all this information you have about probabilities of the bugginess of various optimization passes is really just a millibyte is misleading; you have a lot of information, you're just ignoring it and saying you only care about a millibyte's worth of it.

Post reply on HN