As my project is getting towards the end, again, I'm doing a fair bit of debugging. Every so often, a horrible bug crops up that takes a few days, a week, two weeks to fix. Every time I have one, I try to think, on reflection, what could I have done to fix it quicker?
I've noticed a pattern emerging.
Briefly, bugs take me longer to fix when I allow myself to be seduced into chasing half-formed hypotheses as to what the bug is. These hypotheses often prove ill-founded, leading to wasted time that doesn't often add real data or evidence to your bug search. Really, those intermediate hypotheses are little more than speculation or conjecture.
I'm becoming increasingly aware that the more effective strategy is not to consider hypotheses until as late as possible; instead, concentrate on gathering data, evidence and devising test fixtures. This is a very difficult discipline as people naturally love to formulate hypotheses to explain things. They are seductive. They feel like you've found a short-cut to the solution, you've caught your quarry, the tension of the bug fix is over. You get to announce your triumph.
But it's rare that you fix the most difficult bugs with a single brilliant moment of insight. More often, it takes hours of analysis and evidence gathering. That's the most reliable way to reach a well-founded hypothesis that completely fixes the bug, rather than a partial fix, a temporary fix or a heisenbug fix.
Thursday, 17 May 2012
Thursday, 12 April 2012
Interruption Handling Techniques for Programmers
Once more, I find myself in the post-alpha run to the finish line. And once again, I find myself getting busier and busier as the completion date looms.
One of the most challenging issues at this time is managing the stream of traffic to your desk. Other people are very busy too. People have questions. People need answers. And answering those questions takes time away from handling your own workload, allowing it to multiply like bacteria. I find programmers tend to employ several archetypal techniques to handle those interruptions:
1. Just help them. Indulge them. Offer them as much help as you can. Get their problem fixed, as it helps the team move forward. Really, this is the ideal strategy for the whole project. Someone has come to you with a problem, they may be at their wits end, you should help them fix it.
The problem is that it's a win-win-lose proposition. It's a win for the individual, it's a win for the team, but it's a lose for you.
2. Say you don't know. Strangely, this is a rare tactic. People often feel it's preferable to have a stab, and speculate as to the cause or the solution, even without any useful knowledge or data. Email is rife with this kind of thing. This isn't actually useful. The individual with the problem is likely to have conducted much the same process and reached similar conclusions. It's nice that you're trying, but this just consumes time and doesn't advance a solution. Better to say you don't know, and refer them to someone else who may be able to help.
3. Pretend you don't know. You may know the answer, but since fully helping is a time sink for you, you may judge it more profitable to deny all knowledge and continue work.
Until someone rats you out.
Not a great plan. Not professional. Instead, it's better to admit knowledge where you have it, but if you have a more pressing matter, explain yourself and offer help when you're done. If it's urgent, they can find help elsewhere, if not they can wait. Chances are they'll solve it anyway in the meantime, increasing their own knowledge and learning.
4. Measured help. Give them just enough help to get them moving forward again, but stop short of full disclosure. The advantages to this technique are that you're offering help, the individual is employing their own initiative and learning and everyone gets to move forward. The downside is that they may return to your desk a further 38 times before the problem is solved.
5. Be brusque. Make people not want to ask. This is a win for you, in the short term, but a lose for the team and a lose for yourself in the long term as people will not offer help in return. It can be difficult to resist this strategy when you're stressed!
6. Refer them to a subordinate. The joys of seniority! Pass the problem down the line to the next guy. It's a win for you, but it has mixed results. It may result in a win for the delegate, as they learn something and increase their standing within the team. It may be a win for the individual. It's a win for you, as it frees your time up. The problem is if the delegate cannot solve that problem. The delegate burns a lot of time, the individual with the problem loses time, and ultimately you end up having to help out anyway. Choose carefully.
7. Dazzle them with science. This is a strange one. When faced with a non-technical user, they blaze them with incredible technical knowledge and prowess. A scintillating analysis, definition and solution to the problem is offered; the individual looks back, blankly. No solution is made. The individual retreats, and contacts your line manager to request that you implement the solution instead. You clearly know what you're talking about.
8. Debate them on it. One for the orators. Any problem can be negated with a gallant argument, excellent critical analysis and undeniable logic. Your inquirer retreats, defeated. No more problem you think! No. Instead, the inquirer learns to cut you out of the loop, and ratify and implement a solution elsewhere, elsehow.
9. Blame the build server / Visual Studio / Perforce / Whatever. Clearly the programmer doesn't honestly believe this is the case. It's just a play to buy some time, or to momentarily offload the stress.
10. Counter-problem! You come to me with a problem? You're gonna leave with a bigger one! Thats the Chicago way.
One of the most challenging issues at this time is managing the stream of traffic to your desk. Other people are very busy too. People have questions. People need answers. And answering those questions takes time away from handling your own workload, allowing it to multiply like bacteria. I find programmers tend to employ several archetypal techniques to handle those interruptions:
1. Just help them. Indulge them. Offer them as much help as you can. Get their problem fixed, as it helps the team move forward. Really, this is the ideal strategy for the whole project. Someone has come to you with a problem, they may be at their wits end, you should help them fix it.
The problem is that it's a win-win-lose proposition. It's a win for the individual, it's a win for the team, but it's a lose for you.
2. Say you don't know. Strangely, this is a rare tactic. People often feel it's preferable to have a stab, and speculate as to the cause or the solution, even without any useful knowledge or data. Email is rife with this kind of thing. This isn't actually useful. The individual with the problem is likely to have conducted much the same process and reached similar conclusions. It's nice that you're trying, but this just consumes time and doesn't advance a solution. Better to say you don't know, and refer them to someone else who may be able to help.
3. Pretend you don't know. You may know the answer, but since fully helping is a time sink for you, you may judge it more profitable to deny all knowledge and continue work.
Until someone rats you out.
Not a great plan. Not professional. Instead, it's better to admit knowledge where you have it, but if you have a more pressing matter, explain yourself and offer help when you're done. If it's urgent, they can find help elsewhere, if not they can wait. Chances are they'll solve it anyway in the meantime, increasing their own knowledge and learning.
4. Measured help. Give them just enough help to get them moving forward again, but stop short of full disclosure. The advantages to this technique are that you're offering help, the individual is employing their own initiative and learning and everyone gets to move forward. The downside is that they may return to your desk a further 38 times before the problem is solved.
5. Be brusque. Make people not want to ask. This is a win for you, in the short term, but a lose for the team and a lose for yourself in the long term as people will not offer help in return. It can be difficult to resist this strategy when you're stressed!
6. Refer them to a subordinate. The joys of seniority! Pass the problem down the line to the next guy. It's a win for you, but it has mixed results. It may result in a win for the delegate, as they learn something and increase their standing within the team. It may be a win for the individual. It's a win for you, as it frees your time up. The problem is if the delegate cannot solve that problem. The delegate burns a lot of time, the individual with the problem loses time, and ultimately you end up having to help out anyway. Choose carefully.
7. Dazzle them with science. This is a strange one. When faced with a non-technical user, they blaze them with incredible technical knowledge and prowess. A scintillating analysis, definition and solution to the problem is offered; the individual looks back, blankly. No solution is made. The individual retreats, and contacts your line manager to request that you implement the solution instead. You clearly know what you're talking about.
8. Debate them on it. One for the orators. Any problem can be negated with a gallant argument, excellent critical analysis and undeniable logic. Your inquirer retreats, defeated. No more problem you think! No. Instead, the inquirer learns to cut you out of the loop, and ratify and implement a solution elsewhere, elsehow.
9. Blame the build server / Visual Studio / Perforce / Whatever. Clearly the programmer doesn't honestly believe this is the case. It's just a play to buy some time, or to momentarily offload the stress.
10. Counter-problem! You come to me with a problem? You're gonna leave with a bigger one! Thats the Chicago way.
Saturday, 11 February 2012
R & D - It keeps you honest!
I've recently been working in an R&D group, developing various features that are quite experimental and wouldn't normally be scheduled as part of a project. This is intended to be "practical" R&D - we aim to develop features that have a chance of making it into the game, as opposed to features that are blue sky and would never actually be shipped.
This kind of development approach subtly shifts your approach to developing features. Briefly, you become very focused on doing what is necessary to get the feature into the game. You focus on making sure the feature is on-budget. You make sure that you consult with affected parties. You work out the consequences of incorporating the system and seek to mitigate any problems. You suddenly find yourself becoming a salesman, trying to establish a coalition of support for the feature. Your feature really has to prove itself worthwhile so that management will entertain the perceived risk of incorporating it.
Strangely, you don't always find yourself doing these things during the development of "standard" features. Because they are planned as part of the development effort, their inclusion in the title is automatically assured - pending no major disasters. You don't have to sell them. These features don't need to earn their place. Consequently, it can be very easy to find yourself "going down a rabbit hole" with features like this - exploring functionality that is interesting, but not necessarily focused on shipping. Perhaps these features are ultimately more risk-intensive, as they won't be quite so critically examined as the R&D features.
I tend to find that the whole "posture" you adopt during the development of an R&D feature that is not automatically included in the game is ultimately much better from the perspective of careful software development. It does at least feel more like the kind of process intended by the creators of various software development methodologies. It feels very much along the lines of the approach advocated by Michael Saladino in his "Why Red Lining Your Team Leads to Ineffectiveness".
Perhaps it's not for everyone. Perhaps it's not for every team. Perhaps some may find it quite a pressured, stressful kind of approach. But I really quite like it. It certainly feels a much more considered, deliberate approach. It seems that developing features in branches, that have to prove their worth for integration, sets in motion a slightly changed, more focused set of processes than may be typical.
This kind of development approach subtly shifts your approach to developing features. Briefly, you become very focused on doing what is necessary to get the feature into the game. You focus on making sure the feature is on-budget. You make sure that you consult with affected parties. You work out the consequences of incorporating the system and seek to mitigate any problems. You suddenly find yourself becoming a salesman, trying to establish a coalition of support for the feature. Your feature really has to prove itself worthwhile so that management will entertain the perceived risk of incorporating it.
Strangely, you don't always find yourself doing these things during the development of "standard" features. Because they are planned as part of the development effort, their inclusion in the title is automatically assured - pending no major disasters. You don't have to sell them. These features don't need to earn their place. Consequently, it can be very easy to find yourself "going down a rabbit hole" with features like this - exploring functionality that is interesting, but not necessarily focused on shipping. Perhaps these features are ultimately more risk-intensive, as they won't be quite so critically examined as the R&D features.
I tend to find that the whole "posture" you adopt during the development of an R&D feature that is not automatically included in the game is ultimately much better from the perspective of careful software development. It does at least feel more like the kind of process intended by the creators of various software development methodologies. It feels very much along the lines of the approach advocated by Michael Saladino in his "Why Red Lining Your Team Leads to Ineffectiveness".
Perhaps it's not for everyone. Perhaps it's not for every team. Perhaps some may find it quite a pressured, stressful kind of approach. But I really quite like it. It certainly feels a much more considered, deliberate approach. It seems that developing features in branches, that have to prove their worth for integration, sets in motion a slightly changed, more focused set of processes than may be typical.
Thursday, 9 February 2012
Sparse Voxel Octrees in Haskell
It's been a long time coming (daughters birth impedes Haskell coding!), but I've finally implemented and uploaded support for Sparse Voxel Octrees in my Haskell Renderer.
Alternatively, In Haskell, you can still go for the strict option and implement it much as you would with C.
What's interesting is that it introduces this challenging, general question of what offers the most efficiency: A domain-specific, efficiently implemented clever algorithm, or a somewhat more generic algorithm, less specifically optimised but instead relying on lazy evaluation and the higher-order optimisations that may automatically permit?
I'm not sure what the answer is to this question right now. I suspect there is a cross over point that is very specific to the data set in question and therefore your particular application.
Code
My current Haskell SVO code is on github, in my Haskell Renderer:
I'm going to fix up the various remaining TODOs and then pursue a more optimised, C-like version along the lines of the various SIMD-like SVO implementations that have recently emerged.
This was ultimately quite an elegant algorithm to implement in Haskell. Much of the algorithm is built off simple geometric tests. These are quite compact and elegant to represent in a functional language like Haskell. For instance, a ray-box test is simply:
boundingBoxIntersectRay :: AABB -> Ray -> Maybe (Double, Double)
boundingBoxIntersectRay (bounds0, bounds1) (Ray rayOrg _ invRayDir rayLen)
| tmax > tmin = Nothing
| tmin > 0 && tmin < rayLen = Just (tmin, tmax `Prelude.min` rayLen)
| tmax > 0 && tmax < rayLen = Just (tmax, tmax)
| otherwise = Nothing
where
(tmin, tmax) = foldr1 (\(a0, b0) (a1, b1) -> (a0 `Prelude.max` a1, b0 `Prelude.min` b1)) (map intercepts [vecX, vecY, vecZ])
intercepts f = let x0 = (f bounds0 - f rayOrg) * f invRayDir
x1 = (f bounds1 - f rayOrg) * f invRayDir
in (x0 `Prelude.min` x1, x0 `Prelude.max` x1)
Here we simply define an operation to calculate the slab intercepts of the box, and then repeat that operation over X, Y and Z, then fold to reduce the results. We're offering a description of the algorithm to Haskell in high level primitives, permitting optimisation and reduction - as opposed to clumsily trying to indirectly tell a C++ compiler what you'd really like it to do. It's surprising how often this sort of thing proves faster in Haskell. For example, using the "any" or "all" functions has proven faster than a set of || or && clauses for me in the past. I could really imagine that a thunk-less version of Haskell, free of the irritation of considering C++ aliasing might produce some very efficient code.
The traversal code is a simple recursive traversal, with few (as yet) clever tricks. It terminates either at the leaves, at the maximum traversal depth or when the feature becomes too small when projected to screen space (though this calculation needs further elaboration). It therefore gives a simple, automatic LOD control.
It's quite an interesting algorithm to implement in something like Haskell. It's interesting because it really questions the balance of strict vs lazy evaluation in Haskell. Which is better - strict construction and strict traversal, with the platform optimisations that may bring, or lazy construction-as-you-traverse?
In an imperative language, you'd run a complete process to construct the tree, and then traverse the completed tree for each intersection query. You have to pay the total construction cost plus the traversal cost. Since you'd be constructing and storing the whole tree, you need to invest significant effort in data compression. On the other hand, the direct data representation would permit you to make a number of optimisations aimed at evaluation efficiency.
With Haskell, the lazy evaluation thunks can do some of that work for you. Instead of trying to crunch the whole tree down to be as small as possible, you may choose instead to rely on the Haskell runtime to just-in-time construct the relevant portions of it. You would only pay the cost of construction for the parts of the tree you traverse. Would this sum be lower than a strict construction and traversal?
Alternatively, In Haskell, you can still go for the strict option and implement it much as you would with C.
What's interesting is that it introduces this challenging, general question of what offers the most efficiency: A domain-specific, efficiently implemented clever algorithm, or a somewhat more generic algorithm, less specifically optimised but instead relying on lazy evaluation and the higher-order optimisations that may automatically permit?
I'm not sure what the answer is to this question right now. I suspect there is a cross over point that is very specific to the data set in question and therefore your particular application.
Code
My current Haskell SVO code is on github, in my Haskell Renderer:
I'm going to fix up the various remaining TODOs and then pursue a more optimised, C-like version along the lines of the various SIMD-like SVO implementations that have recently emerged.
Implementation Notes
This was ultimately quite an elegant algorithm to implement in Haskell. Much of the algorithm is built off simple geometric tests. These are quite compact and elegant to represent in a functional language like Haskell. For instance, a ray-box test is simply:
boundingBoxIntersectRay :: AABB -> Ray -> Maybe (Double, Double)
boundingBoxIntersectRay (bounds0, bounds1) (Ray rayOrg _ invRayDir rayLen)
| tmax > tmin = Nothing
| tmin > 0 && tmin < rayLen = Just (tmin, tmax `Prelude.min` rayLen)
| tmax > 0 && tmax < rayLen = Just (tmax, tmax)
| otherwise = Nothing
where
(tmin, tmax) = foldr1 (\(a0, b0) (a1, b1) -> (a0 `Prelude.max` a1, b0 `Prelude.min` b1)) (map intercepts [vecX, vecY, vecZ])
intercepts f = let x0 = (f bounds0 - f rayOrg) * f invRayDir
x1 = (f bounds1 - f rayOrg) * f invRayDir
in (x0 `Prelude.min` x1, x0 `Prelude.max` x1)
Here we simply define an operation to calculate the slab intercepts of the box, and then repeat that operation over X, Y and Z, then fold to reduce the results. We're offering a description of the algorithm to Haskell in high level primitives, permitting optimisation and reduction - as opposed to clumsily trying to indirectly tell a C++ compiler what you'd really like it to do. It's surprising how often this sort of thing proves faster in Haskell. For example, using the "any" or "all" functions has proven faster than a set of || or && clauses for me in the past. I could really imagine that a thunk-less version of Haskell, free of the irritation of considering C++ aliasing might produce some very efficient code.
The traversal code is a simple recursive traversal, with few (as yet) clever tricks. It terminates either at the leaves, at the maximum traversal depth or when the feature becomes too small when projected to screen space (though this calculation needs further elaboration). It therefore gives a simple, automatic LOD control.
And so, finally, here it is, our SVO lego-sphere:
Thursday, 2 February 2012
Peak Abstraction
An interesting phenomena I've observed over my years as a programmer is the occurrence of "Peak Abstraction" within a young programmer - and their subsequent improvement.
There is a common pattern. It typically occurs after 3-4 years of professional practice. A programmer is growing in his confidence. He begins to tackle more complex, challenging problems. And, he reflects those problems with complex, challenging data structures. He has not yet learnt the fine art of simplicity.
Every member of every data structure is a pointer or a reference. There are no simple data types. Everything becomes a "value dictionary", a "graph-based visitor" or a "multi-dimensional ring buffer". Disassembly of his code reveals it to be little more than an infinite sequence of lwz, lwz, lwz, lwz and more lwz. Perhaps he/she develops a hobbyist interest in Java. They may develop an editor that connects boxes with lines - such editors are great for filling with lots and lots of abstraction! Often, she/he may favour Boost; perhaps he even becomes your office's Boost Guy. Even simple plain old data types such as integers are suddenly held within a smart-pointer container and reference counted. And with a pimpl to retrieve their value.
Those around them become increasingly desperate. They can see the code becoming inflated, inefficient, unmaintainable. Spending time reading this individual's code is like spending time exposed to a radioactive isotope. You can only tolerate a few moments before exhibiting signs of sickness. You attempt to modify their code. 478 pages of template errors dissuade you from considering this foolish course of action again.
And then it happens. The programmer realises the error of their ways. They realise that they are adding neither design value nor computational value. They realise they are adding overhead and maintenance trouble. Perhaps they undergo their first encounter with profiling software. Said software may disclose the full terror of the D$ dirty bomb they have unleashed upon the code. Perhaps they are "introduced" to the profiler by an irate lead in some sort of shotgun-wedding affair. Whatever, the programmer realises that solving complex problems does not require needlessly complex data structures. Such structures impress nobody. People are impressed by simple, elegant solutions. And thus the recovery begins. Data structures become simple, expressive, and maintainable. Data cache misses dip under 20ms/frame for the first time. Co-workers enjoy modifying their code. The compiler begins to emit instructions such as "add" or "mul". Sadly the compiler may be too fond of outputting "jump" instructions at this stage... The programmer themself becomes wary of others who are pre-Peak Abstraction.
One even wonders if, like it's namesake "Peak Oil", there may be a global Peak Abstraction. Perhaps the practising body of programmers may all undergo Peak Abstraction in the next 5-10 years and we will all left never having to refactor some template monstrosity.
But then, where's the fun in that? Don't programmers just love to be indignant about others' code?
Tuesday, 13 September 2011
Haskell Photon Mapper Released to Hackage
I've now uploaded my Haskell photon mapper and raytracer to hackage. It is listed as a package called "crocodile" (named after my son's current obsession with crocodiles!).
It's all working on the Cornell box. It's pretty memory hungry, and has a few self-declared things to fix (eg irradiance gradients), but it's out there to play with.
Enjoy.
It's all working on the Cornell box. It's pretty memory hungry, and has a few self-declared things to fix (eg irradiance gradients), but it's out there to play with.
Enjoy.
Thursday, 25 August 2011
This is what happens
When universities teach Java!
(some random bit of disassembled code found on my travels)
00A5CA74 EC7E1824 fdivs f3,f30,f3 56 PIPE
00A5CA78 FC406850 fneg f2,f13
00A5CA7C D0660010 stfs f3,0x10(r6)
00A5CA80 D0C90010 stfs f6,0x10(r9)
00A5CA84 D981FF60 stfd f12,-0xA0(r1) PIPE
00A5CA88 E881FF60 ld r4,-0xA0(r1) 70 (00A5CA84) LHS[01]
00A5CA8C D961FF60 stfd f11,-0xA0(r1) PIPE
00A5CA90 EBA1FF60 ld r29,-0xA0(r1) 70 (00A5CA8C) LHS[01]
00A5CA94 D941FF60 stfd f10,-0xA0(r1) PIPE
00A5CA98 EB81FF60 ld r28,-0xA0(r1) 70 (00A5CA94) LHS[01]
00A5CA9C D921FF60 stfd f9,-0xA0(r1) PIPE
00A5CAA0 EB61FF60 ld r27,-0xA0(r1) 70 (00A5CA9C) LHS[01]
00A5CAA4 D901FF60 stfd f8,-0xA0(r1) PIPE
00A5CAA8 EB41FF60 ld r26,-0xA0(r1) 70 (00A5CAA4) LHS[01]
00A5CAAC D8E1FF60 stfd f7,-0xA0(r1) PIPE
00A5CAB0 EB21FF60 ld r25,-0xA0(r1) 70 (00A5CAAC) LHS[01]
00A5CAB4 D1A6000C stfs f13,0xC(r6) PIPE
00A5CAB8 D029000C stfs f1,0xC(r9)
00A5CABC D801FF60 stfd f0,-0xA0(r1) PIPE
00A5CAC0 E801FF60 ld r0,-0xA0(r1) 70 (00A5CABC) LHS[01]
0
(some random bit of disassembled code found on my travels)
00A5CA74 EC7E1824 fdivs f3,f30,f3 56 PIPE
00A5CA78 FC406850 fneg f2,f13
00A5CA7C D0660010 stfs f3,0x10(r6)
00A5CA80 D0C90010 stfs f6,0x10(r9)
00A5CA84 D981FF60 stfd f12,-0xA0(r1) PIPE
00A5CA88 E881FF60 ld r4,-0xA0(r1) 70 (00A5CA84) LHS[01]
00A5CA8C D961FF60 stfd f11,-0xA0(r1) PIPE
00A5CA90 EBA1FF60 ld r29,-0xA0(r1) 70 (00A5CA8C) LHS[01]
00A5CA94 D941FF60 stfd f10,-0xA0(r1) PIPE
00A5CA98 EB81FF60 ld r28,-0xA0(r1) 70 (00A5CA94) LHS[01]
00A5CA9C D921FF60 stfd f9,-0xA0(r1) PIPE
00A5CAA0 EB61FF60 ld r27,-0xA0(r1) 70 (00A5CA9C) LHS[01]
00A5CAA4 D901FF60 stfd f8,-0xA0(r1) PIPE
00A5CAA8 EB41FF60 ld r26,-0xA0(r1) 70 (00A5CAA4) LHS[01]
00A5CAAC D8E1FF60 stfd f7,-0xA0(r1) PIPE
00A5CAB0 EB21FF60 ld r25,-0xA0(r1) 70 (00A5CAAC) LHS[01]
00A5CAB4 D1A6000C stfs f13,0xC(r6) PIPE
00A5CAB8 D029000C stfs f1,0xC(r9)
00A5CABC D801FF60 stfd f0,-0xA0(r1) PIPE
00A5CAC0 E801FF60 ld r0,-0xA0(r1) 70 (00A5CABC) LHS[01]
0
Subscribe to:
Posts (Atom)