Suppose you are a building contractor. You have given start dates for future jobs, but your current job is going to run over the expected time. You can choose between:
1 slip every job, annoying all of the customers whose jobs are queued up. You get a bad reputation.
2 Move onto the next job on time, and gradually complete the stalled job in the background by sending workers back to it when you have spare (which you should have, because in general you must overestimate or things will go badly wrong).
That customer will now suffer because their job is going to take a multiple of the expected time, but all of the other customers are happy, so your reputation is good.
I had a section in the post I cut out about how optimizing queue selection started out as a technical problem, but transformed into more of a business and ethical problem the more I pondered it.
You're effectively deciding how to distribute suffering across a large group of people.
Comes up in any situation where large metric gains can be accomplished by optimizing for specific groups - recommender and personalization systems are another example.
Not the OP, but Fyi you know that to some extent anyway, because the termination condition is that confidence is above a specified value. This is one of the advantages over just doing git bisect with some finger-in-air test repeat factor.
But yeah it can print that too.
It's worth noting that the analysis (although not this specific algorithm) applies in cases where there is a deterministic approach, but a nondeterministic algorithm is faster.
For example, suppose you have some piece of hardware which you can interrogate, but not after it crashes. It crashes at a deterministic point. You can step it forward by any amount of steps, but only examine it's state if it did not crash. If it crashed, you have to go back to the start. (I call this situation "Finnegan Search", after the nursery rhyme which prominently features the line "poor old Finnegan had to begin again").
The deterministic algorithm has you do an examination after every step. The nondeterministic algorithm has you choose some number of steps, accepting the risk that you have to go back to the start. The optimal number of steps (and thus the choice of algorithm) depends on the ratio of the cost of examination to the cost of a step. It can be found analytically as the expected information gain per unit time.
(Either way the process is pretty annoying and considerable effort in hardware and software design has gone into providing ways to render it unnecessary, but it still crops up sometimes in embedded systems).
In theory, the algorithm could deal with that by choosing the commit at each step, which gives the best expected information gain; divided by expected test time. In most cases it would be more efficient just to cache the compiled output though.
This doesn't sound quite right, but I'm not sure why.
Perhaps: a reasonable objective would be to say that for N bits of information, I would like to pick the test schedule that requires the least total elapsed time. If you have two candidate commits and a slow recompile time, it seems like your algorithm would do many repeats of commit A until the gain in information per run drops below the expected gain from B divided by the recompile time, then it would do many repeats of B, then go back to A, etc. So there are long runs, but you're still switching back and forth. You would get the same number of bits by doing the same number of test runs for each commit, but batching all of the A runs before all of the B runs.
Then again: you wouldn't know how many times to run each in advance, and "run A an infinite number of times, then run B an infinite number of times" is clearly not a winning strategy. Even with a fixed N, I don't think you could figure it out without knowing the results of the runs in advance. So perhaps your algorithm is optimal?
It still feels off. You're normalizing everything to bits/sec and choosing the maximum. But comparing an initial test run divided by the rebuild time vs a subsequent test run divided by a much faster time seems like you're pretending a discrete thing is continuous.
The general requirement for this approach to be optimal, is called "dynamical consistency". A good description is in [1]. It is the situation where, suppose you have a budget B , and you search until your budget is exhausted. Then you are informed that there is an additional budget, B2, and you can continue searching until that is exhausted. A situation is dynamically consistent if, for any B,B2, the optimal strategy is such that you would make the same choices whether you know that you will get B2 or not.
So you are correct that discreteness is a problem, because if you are nearing the end of the budget you may optimally prefer to get more dice rolls than take bigger bets. But the optimal solution is then often analytically intractable (or at least it was - I last read about this a while back), and the entropy approach is often reasonable anyway. (For cases where search effort is significant, a good search plan can be found by simulation).
Note that "pick the commit with best expected information gain" in git_bayesect isn't optimal even in the no overhead regime. I provide a counterexample in the writeup, which implies ajb's heuristic is also not optimal. I don't see a tractable way to compute the optimal policy.
One idea: if you always spend time testing equal to your constant overhead, I think you're guaranteed to be not more than 2x off optimal.
(and agreed with ajb on "just use ccache" in practice!)
I'm going to have to check out how you got linear time with Shannon entropy, because I used Renyi entropy to do that, to make the algebra easier.
It's also possible to do it over the DAG, rather than a linear history - although that makes the code a lot more complicated. Unfortunately there doesn't seem to be a linear time cumulative sum algorithm over dags, so it's super linear in some cases.
The UK regs update[1] mentions a battery, but you have to pay for it so I don't have the details.
It appears your could legally install one of these panels on the 15th of this month, but there presumably won't be any certified to comply with the regs on sale yet.
(That seems to be an archive of the old revctrl.org pages from a while back; most likely Bram Cohen has a blog somewhere explaining it in his own words - probably about 2003, at a guess)
Interesting observations. The design of cat flaps does seem suboptimal. I had not thought about the shape- it seems a good call that tall and thin would be better - but also the hinge at the top allows the flap to fall on the tail.
Okay, so when you, BobbyJo, become too old or unwell to work; other people should just shoot you in the head and take your stuff, right? It would only be efficient. Or does this 'harsh reality" only apply to other people?
Modern society has the luxury of surplus resources at the moment, and we are able to take care of the old and weak, which we indeed choose to do. If/when that ceases to be the case, the harsh reality will apply to everyone, me included, yes.
Another thing humans are arguably good at is making a longer term plan and investment: if we see that old people simply get shot, we won't be investing surplus value into our retirement funds — at least not of the same sort. Perhaps we'll be building fortresses when younger, accumulating wealth to be able to pay soldiers to protect us etc...
Wait, that's exactly what has happened, except it has evolved into a more systemic solution (our taxes and social contributions pay for police, courts; bigger accumulated wealth allows for more options...).
1 slip every job, annoying all of the customers whose jobs are queued up. You get a bad reputation.
2 Move onto the next job on time, and gradually complete the stalled job in the background by sending workers back to it when you have spare (which you should have, because in general you must overestimate or things will go badly wrong). That customer will now suffer because their job is going to take a multiple of the expected time, but all of the other customers are happy, so your reputation is good.
reply