search

ndmitchell / rattle

Forward build system with speculation and caching
Other
102 stars 5 forks source link

Review Hazard #18

Open ndmitchell opened 4 years ago

ndmitchell commented 4 years ago

The patch in https://github.com/ndmitchell/rattle/commit/170981ca947cf6446f2857d6db32b8b8e350b02c changes Hazard set merging, which I got wrong in the past. It removes the requirement to find when a command was speculated (which means doing it in O(log n) is way easier). I think it subtly changes the nature of a hazard, but in ways that improve it. Would be good for @spall to carefully review it.

On the plus side, after reworking that code, I completely understand the hazards/speculation stuff @spall was talking about in #13.

ndmitchell commented 4 years ago

I suggest reviewing it in it's current state - there was one bug I introduced, just fixed.

spall commented 4 years ago

write before read: This looks good to me, and i'm gonna type out my logic here in case I am wrong.

There are 4 possiblities:

  1. write speculated -> read required => Restart
  2. write speculated -> read speculated => OK ( but maybe bad later)
  3. write required -> read speculated => OK
  4. write required -> read required => OK!
    Originally I thought in the case of (4) it was necessary to check the order of the read and write in the required list, but after careful thought I see that isn't necessary, so this is a nice simplification.
    With regards to the case where both were speculated (2), a possibility that i don't think this version or the previous version handled was what if both of those commands are later required in the reverse order? That would be a non-recoverable hazard rattle would accidentally not notice right?

read before write: This one also looks good to me except I think the 3rd condition (where order in required list is checked) should be Recoverable and not Restartable?? Because Rattle began by speculating the read too soon...

  1. read speculated -> write required => Recover; handled by first case
  2. read speculated -> write speculated => Recover; handled by first case
  3. read required -> write speculated => Restart; handled by 2nd case
  4. read required -> write required => Recoverable or NonRecoverable; handled by last 2 cases.