In both my personal and my work projects I prefer to use
git rebase
to keep my commit histories simple and readable.
To make this work in a team setting, we never work on the master
branch, instead always working on a feature branch in our local repositories.
Our process flow looks something like this:
$ git branch feature #create the working branch
$ git checkout feature #do all development work on that branch
#Edit files, etc.
$ git commit -m "Implement Feature"
#Repeat the above as desired during development.
#When ready to merge to master, do the following:
$ git checkout master
$ git pull #update master from shared repository
$ git checkout feature
$ git rebase master #optionally with -i if squashing is desired
$ git checkout master
$ git merge feature
$ git push origin master
$ git branch -d feature
Because we never use our local master branch for development, the
git pull on master is always a
fast-forward merge.
Likewise, because we have just rebased the feature branch against the master
right before we merge that feature branch back into master, that merge is also
always a fast-forward merge.
Looking at it another way, we don't have any merge conflicts when
updating or merging master because we resolve all of the merge
conflicts when we rebase the feature branch against the latest master.
The Problem
At work, we have a large codebase and a handful of active developers who
typically merge feature branches to the master using the above workflow
multiple times each day. Sometimes somebody has a feature branch that
takes a long time to finish, so that between the time that branch was
started and the time it is ready to go into master, there may
have been 40 or 50 other commits made to master.
In general in this situation we will occasionally rebase our local
feature branch against the latest master a few times during feature
development, but inevitably there are occasions when a large rebase
across many commits ends up being done.
Even if there are many commits on the master branch,
if none of those commits touched any of the same code as the commits
on the feature branch, then there should be no merge conflicts when
rebasing the feature branch against the updated main branch.
However, in my experience this has not always been the case.
Sometimes git rebase reports merge conflicts when I think there
should not be any.
Since I don't generally know exactly what code the other team members have
edited, I can't immediately tell if the merge conflicts make sense.
The normal advice for how to handle merge conflicts is to edit the named
file, look for the conflict markers, inspect the conflicting code fragments,
determine what to keep, edit out what is not being kept along with the
conflict markers, git add the repaired file, and
git rebase --continue to let it tell you about the next merge conflict.
That's a lot of work, and it might all be completely unnecessary.
The Solution
It seems that git sometimes just gets confused when doing a rebase across
a large number of commits.
Sometimes if you rebase in smaller steps, git will happily rebase each
smaller step with no merge conflicts, until you have stepped all the way
up to the latest master, at which point your rebase is done.
You could rebase against every single commit and work your way up to master,
but that, too, is a lot of work.
Here's what I do when the initial rebase of the feature branch against
the latest master tells me there are merge conflicts.
When the initial git rebase reports a merge conflict,
I immediately do git rebase --abort to undo that rebase attempt.
Using gitk --all to view the commit tree, which lets me see
the master branch and the commit at which my feature branch branches
off the master branch, I select a commit on the master branch
about half way between those two commits.
I copy the commit ID and paste it into a rebase command that looks
something like this:
$ git rebase 8bc85584989e4435c2d98b13447bcab37648ba7f
If this rebase reports no merge conflicts, then I try rebasing
against master and repeat the process.
If there are merge conflicts, then I abort the rebase and pick another
commit half way again to the branch point.
I repeat this until either the rebase succeeds or I am trying to
rebase across a single commit.
At that point, if there are still merge conflicts, they are real
and I address them in the normal way.
Since the conflict is only across a single commit, it is easier to
see the cause of the conflict and to resolve it.
After resolving the conflict across that one commit,
I go back to the first step and try rebasing against master again,
repeating the process.
I have followed this process a number of times.
I think that a majority of these times I binary-divide my commits
a few times and end up piecemeal stepping through the commits
until I have rebased against master without ever having to resolve
any conflicts.
The other times I typically have to resolve one or two small conflicts,
after which I can rebase against master.
The next time you do a rebase across more than one commit and git
tells you there are merge conflicts, try this approach.
You might save yourself a lot of work.
We are often asked to rate things on a scale, typically 1 to 5 or 1 to 10.
Rarely is there an attempt to define what those different numbers mean.
From a statistician's point of view, this makes the values useful for the
sole purpose of comparing a single individual's ratings against other ratings
of that individual.
In particular, without a good definition of what the various levels mean,
I don't see how there can be any effective communication from one person to
another of the meaning of such a rating.
When my doctor asks me to tell him how much something hurts on a scale
of 1 to 10, I have no idea what information he expects to get when I say
"3" or "7".
I once asked an acquaintance to rate, on a scale of 1 (bad) to 10 (good),
a movie he had just seen. He said it was a 9. I was suspicious of this
answer, so I asked him how he would rate Star Wars, which I knew to be
his all-time favorite movie, on the same 1-to-10 scale. He said 12.
I personally consider it an aspect of innumeracy, but people often try to
emphasize something by using numbers that are outside of the valid range.
We may chuckle when Nigel says he likes his amp better because it
goes to 11, but how often have you heard someone talking in all
seriousness about putting in a "110% effort"?
What does that actually
mean?
How would you know if someone were
putting in
110% versus 100%?
If 110% is a valid number, then presumably
so is 120%,
so anyone
suggesting a mere 110%
is clearly not asking for enough effort.
People tend to
overestimatehow good
they are at all sorts of things,
including cognitive, social and physical skills.
If we all overrate ourselves by the same amount, I suppose that could all cancel
out and you could still compare people's ratings -
but without knowing a priori
what their ratings should be, we don't know how much they might be
overrating themselves.
When people consider their own expertise, it is common for those with less
expertise to overvalue themselves more than people with more expertise.
With more expertise comes more awareness of what one could do better.
Einstein
said,
"As our circle of knowledge expands, so does the circumference of darkness surrounding it."
Relative beginners easily fall into the
Sophomore Illusion
of thinking they
know a lot because the circumference of their knowledge is not yet large
enough for them to recognize the size of the surrounding darkness.
In 1989, psychologist
John Hayes
at Carnegie Mellon University
identified what is now called the "ten-year rule"
(although there are
earlier commenters,
including Herbert Simon,
who was also at CMU).
As
Leonard Mlodinow
says in
"The Drunkard's Walk",
"Experts often speak of the
'ten-yearrule,'
meaning that it takes at least a decade of hard work, patience and striving
to become highly successful in most endeavors." (links mine)
The ten-year rule is related to the idea that it takes about 10,000 hours
of practice at something to become an expert; with 5 hours of practice
per business day and 200 business days per year,
it would take ten years to rack up that many hours.
If you find yourself thinking how wonderfully expert you are in something
that you have practiced for only a few years, perhaps you should
consider the ten-year rule and temper your evaluation.
Given that people are so bad at these ratings, it seems to me that the only
way to get any useful information from someone when asking this kind of
self-rating question is to have an objective definition
of what each level means.
One way to think about a scale is by how many people fall into each level.
There are currently
7 billion people
in the world,
or almost 10 to the 10th power.
This conveniently maps to a logarithmic scale from 0 to 10,
allowing us to define eleven levels starting with level 0
containing all approximately 10 billion people in the world
and with each higher level having one tenth
the number of people as the level just below it.
If the descriptions of a level are hard to interpret,
perhaps the size of that level will help give an indication
of whether a person should be rated there.
Years ago, during a job interview, I was asked to rate my level
of expertise in various subjects, such as programming languages
and development tools.
This was not an unusual question, I had been asked this question
before and have been asked it since.
What was different that time was that the interviewer included
a scale with some relatively objective descriptions for determining
level of expertise.
I rather liked the scale, so
although I don't recall the exact definition of his levels,
I have tried to reproduce that concept here,
using descriptions somewhat similar to those given by that interviewer.
Unfortunately, I don't remember who introduced that scale
to me, so I am unable to give credit.
There are many reasons one might want a scale of expertise,
including rating potential employees or creating a summary
of the amount of expertise within a company.
The scale I present here is intended to be very general;
given its logarithmic nature that can include the
entire world population, it is capable of allowing comparison of
expertise across everyone in the world.
You might think that would make it suboptimal for
rating (potential) employee expertise,
but I think there are enough levels to make it useful for that purpose.
Scale
The scale below includes the following columns:
Level: a number for the level, from 0 to 10,
with 10 being the highest level of expertise.
Name: a name for the level.
These are taken from a set of expertise level names proposed by the
Traveling School of Life.
My use of them probably doesn't quite match their intent,
but I liked the names and thought the ten words matched my
levels pretty well, so I applied them to my levels
and added "ignorant" for level 0.
Description: a brief description of the level.
The descriptions are worded as if for a technical tool;
for application to other areas or concepts, modify accordingly.
Comments referring to companies assume a large company (10,000+ people)
with large divisions (1000+ people);
being a company-wide guru in a company with 100 people
might not get you past level 6.
Size: the approximate number of people expected to be at that level
worldwide.
As mentioned above, this is a simple logarithmic scale.
The number of people in a level is 1010-L where
L is the level number.
Practice: the approximate amount of practice that could be required
to reach that level of expertise.
Putting in that many hours does not guarantee reaching that level,
and reaching that level does not necessarily require
putting in that many hours.
The conversion factors are 1,000 hours per year or 5 hours per day.
All of these different factors are rough estimates,
not intended as absolutes but merely as guidelines to help
people rank themselves in a way that allows for more meaningful results.
I don't have any research to show how well my guesses about
Description, Size and Practice correlate;
if anyone knows of something along those lines,
that would be interesting.
Level
Name
Description
Size
Practice
0
ignorant
I have never heard of it.
10,000,000,000
none
1
interested
I have heard a little about it, but don't know much.
1,000,000,000
1 hour
2
pursuing
I have read an article or two about it and understand the basics
of what it is, but nothing in depth.
100,000,000
1 day (5 hours)
3
beginner
I have read an in-depth article, primer, or how-to book,
and/or have played with it a bit.
10,000,000
1 week (25 hours)
4
apprentice
I have used it for at least a few months and have successfully
completed a small project using it.
1,000,000
3 months (250 hours)
5
intermediate
I have used it for a year or more on a daily or regular basis,
and am comfortable using it in moderately complex projects.
100,000
1 year (1,000 hours)
6
advanced
I have been using it for many years, know all of the basic aspects,
and am comfortable using it as a key element in complex projects.
People in my group come to me with their questions.
10,000
5 years (5,000 hours)
7
accomplished
I am a local expert, with ten or more years of solid experience.
People in my division come to me with their questions.
1,000
10 years (10,000 hours)
8
master
I am a company-wide guru with twenty or more years of experience;
people from other divisions come to me with their questions.
100
20 years (20,000 hours)
9
grandmaster
I am a recognized international authority on it.
10
30 years (30,000 hours)
10
great-grandmaster
I created it, and am the number 1 expert in the world.
1
50 years (50,000 hours)
References
Other scales of expertise:
Ted Neward describes four levels in his
post of August 16:
Apprentice, Journeyman, Master, Adept.
Paul Schempp's take on Dreyfus's five levels,
with "Capable" rather than "Advanced Beginner".
The
Four Stages of Competence of Thomas Gordon:
Unconscious Incompetence, Conscious Incompetence,
Conscious Competence, Unconscious Competence.
And how they might apply to
programming.
In a recent comment on my 2008
blog post
about Scala's parser combinators,
a reader asked how one might go about debugging such a parser.
As
one post
says,
"Debugging a parser implemented with the help of a combinator library
has its special challenges."
You may have trouble
setting breakpoints,
and stack traces can be
difficult to interpret.
The two techniques I show here may not provide you with the kind of
visibility you might be used to when single-stepping through problem code,
but I hope they provide at least a little more visibility than you might
otherwise have.
Example Parser
As an example parser I will use an integer-only version of the
four-function arithmetic parser I
built for my 2008 parser combinator post.
The code consists of a set of case classes to represent the parsed results
and a parser class that contains the parsing rules and a few helper methods.
You can copy this code into a file and either compile it or load it into
the Scala REPL.
import scala.util.parsing.combinator.syntactical.StandardTokenParsers
sealed abstract class Expr {
def eval():Int
}
case class EConst(value:Int) extends Expr {
def eval():Int = value
}
case class EAdd(left:Expr, right:Expr) extends Expr {
def eval():Int = left.eval + right.eval
}
case class ESub(left:Expr, right:Expr) extends Expr {
def eval():Int = left.eval - right.eval
}
case class EMul(left:Expr, right:Expr) extends Expr {
def eval():Int = left.eval * right.eval
}
case class EDiv(left:Expr, right:Expr) extends Expr {
def eval():Int = left.eval / right.eval
}
case class EUMinus(e:Expr) extends Expr {
def eval():Int = -e.eval
}
object ExprParser extends StandardTokenParsers {
lexical.delimiters ++= List("+","-","*","/","(",")")
def value = numericLit ^^ { s => EConst(s.toInt) }
def parens:Parser[Expr] = "(" ~> expr <~ ")"
def unaryMinus:Parser[EUMinus] = "-" ~> term ^^ { EUMinus(_) }
def term = ( value | parens | unaryMinus )
def binaryOp(level:Int):Parser[((Expr,Expr)=>Expr)] = {
level match {
case 1 =>
"+" ^^^ { (a:Expr, b:Expr) => EAdd(a,b) } |
"-" ^^^ { (a:Expr, b:Expr) => ESub(a,b) }
case 2 =>
"*" ^^^ { (a:Expr, b:Expr) => EMul(a,b) } |
"/" ^^^ { (a:Expr, b:Expr) => EDiv(a,b) }
case _ => throw new RuntimeException("bad precedence level "+level)
}
}
val minPrec = 1
val maxPrec = 2
def binary(level:Int):Parser[Expr] =
if (level>maxPrec) term
else binary(level+1) * binaryOp(level)
def expr = ( binary(minPrec) | term )
def parse(s:String) = {
val tokens = new lexical.Scanner(s)
phrase(expr)(tokens)
}
def apply(s:String):Expr = {
parse(s) match {
case Success(tree, _) => tree
case e: NoSuccess =>
throw new IllegalArgumentException("Bad syntax: "+s)
}
}
def test(exprstr: String) = {
parse(exprstr) match {
case Success(tree, _) =>
println("Tree: "+tree)
val v = tree.eval()
println("Eval: "+v)
case e: NoSuccess => Console.err.println(e)
}
}
//A main method for testing
def main(args: Array[String]) = test(args(0))
}
In the ExprParser class, the lines up to and including the
definition of the expr method define the parsing rules,
whereas the methods from parse onwards are helper methods.
Calling Individual Parsers
In our example parser we can easily ask it to parse a string by calling
our ExprParser.test method, which parses the string using our
parse method, prints the resulting parse, and
(if the parse was successful) evaluates the parse tree and prints that value.
The last line of parse
parses a string using our expression parser:
phrase(expr)(tokens)
phrase is a method in
StandardTokenParsers
that parses an input stream using the specified parser.
The only thing special about our expr method is that we
happen to have selected it as our top-level parser -
but we could just as easily have picked one of our other parsers
as our top-level parser.
Let's add another version of the test method that lets us
specify which parser to use as the top-level parser.
We want to print out the results in the same way as for the existing
test method, so we first
refactor that existing method:
def test(exprstr: String) =
printParseResult(parse(exprstr))
def printParseResult(pr:ParseResult[Expr]) = {
pr match {
case Success(tree, _) =>
println("Tree: "+tree)
val v = tree.eval()
println("Eval: "+v)
case e: NoSuccess => Console.err.println(e)
}
}
Now we add a new parse method that accepts a parser as
an argument, and we call that from our new test method:
def parse(p:Parser[Expr], s:String) = {
val tokens = new lexical.Scanner(s)
phrase(p)(tokens)
}
def test(p:Parser[Expr], exprstr: String) =
printParseResult(parse(p,exprstr))
We can run the Scala REPL, load our modified file using the ":load" command,
then manually call the top-level parser by calling our test
method.
To reduce typing, we import everything from ExprParser.
In the examples below, text in bold is what we type,
the rest is printed by the REPL.
We can also call the test method that takes a parser as an
argument, allowing us to specifically test one particular parsing rule
at a time.
If we pass in expr as the parser, we will get the same
results as above;
but if we pass in a different parser, we may get different results.
scala> test(expr,"1+2*3")
Tree: EAdd(EConst(1),EMul(EConst(2),EConst(3)))
Eval: 7
scala> test(binary(1),"1+2*3")
Tree: EAdd(EConst(1),EMul(EConst(2),EConst(3)))
Eval: 7
scala> test(binary(2),"1+2*3")
[1.2] failure: ``/'' expected but `+' found
1+2*3
^
scala> test(parens,"1+2")
[1.1] failure: ``('' expected but 1 found
1+2
^
scala> test(parens,"(1+2)")
Tree: EAdd(EConst(1),EConst(2))
Eval: 3
scala> test(parens,"(1+2)*3")
[1.6] failure: end of input expected
(1+2)*3
^
Tracing
If you have a larger parser that is not behaving and you are not quite
sure where the problem lies, it can be tedious to directly call
individual parsers until you find which one is misbehaving.
Being able to trace the progress of the whole parser running on an
input known to cause the problem might be helpful, but sprinkling
println statements throughout your parser can be tricky.
This section provides an approach that allows you to do some tracing
with minimal changes to your code.
The output can get pretty verbose, but
at least this will give you a starting point from which you may be
able to devise your own improved debugging.
The idea behind this approach is to wrap some or all of the individual
parsers in a debugging parser that delegates its apply action
to the wrapper parser, but that prints out some debugging information.
The apply action is called during the act of parsing.
Note: this code relies on the fact that the code
for the various combinators in
the Parser class in Scala's
StandardTokenParsers
(which is implemented as an inner class in
scala.util.parsing.combinator.Parsers)
does not override any Parser
method other than apply.
This code could be added directly to the ExprParser class,
but it is presented here as a separate class to make it easier to reuse.
Add this DebugStandardTokenParsers class
to the file containing ExprParsers.
trait DebugStandardTokenParsers extends StandardTokenParsers {
class Wrap[+T](name:String,parser:Parser[T]) extends Parser[T] {
def apply(in: Input): ParseResult[T] = {
val first = in.first
val pos = in.pos
val offset = in.offset
val t = parser.apply(in)
println(name+".apply for token "+first+
" at position "+pos+" offset "+offset+" returns "+t)
t
}
}
}
The Wrap class provides the hook into the apply
method that we need in order to print out our trace information as the
parser runs.
Once this class is in place, we modify ExprParser to
inherit from it rather than from StandardTokenParsers:
So far we have not changed the behavior of the parser, since we have not
yet wired in the Wrap class.
To do so, we can take any of the existing parsers and wrap it in a
new Wrap.
For example, with the top-level expr parser
we could do this,
with the added code highlighted in bold:
def expr = new Wrap("expr", ( binary(minPrec) | term ) )
We can make this a bit easier to edit and read by using implicits.
In DebugStandardTokenParsers we add this method:
implicit def toWrapped(name:String) = new {
def !! = new Wrap(name,p)
}
Now we can wrap our expr method like this:
def expr = "expr" !!! ( binary(minPrec) | term )
If you don't like using !!! as an operator, you are free
to pick something more to your taste, or you can leave out the implicit
and just use the new Wrap approach.
At this point you must modify your source code by adding the above syntax
to each parsing rule that you want to trace.
You can go through and do them all, or you can just pick out the ones
you think are the most likely culprits and wrap those.
Note that you can wrap any parser this way, including those that appear
as pieces in the middle of other parsers.
The following example shows how some of the parsers in the term
and binaryOp methods can be wrapped:
Assuming we have wrapped the expr, term and
binaryOp methods as in the above examples, here is what the
output looks like for a few tests.
As in the previous REPL example, user input is in bold.
If you are using the REPL and reload the file, remember to
run import ExprParser._ again to pick up the
newer definitions.
scala> test("1")
term.apply for token 1 at position 1.1 offset 0 returns [1.2] parsed: EConst(1)
plus.apply for token EOF at position 1.2 offset 1 returns [1.2] failure: ``+'' expected but EOF found
1
^
minus.apply for token EOF at position 1.2 offset 1 returns [1.2] failure: ``-'' expected but EOF found
1
^
expr.apply for token 1 at position 1.1 offset 0 returns [1.2] parsed: EConst(1)
Tree: EConst(1)
Eval: 1
scala> test("(1+2)*3")
term.apply for token 1 at position 1.2 offset 1 returns [1.3] parsed: EConst(1)
plus.apply for token `+' at position 1.3 offset 2 returns [1.4] parsed: +
term.apply for token 2 at position 1.4 offset 3 returns [1.5] parsed: EConst(2)
plus.apply for token `)' at position 1.5 offset 4 returns [1.5] failure: ``+'' expected but `)' found
(1+2)*3
^
minus.apply for token `)' at position 1.5 offset 4 returns [1.5] failure: ``-'' expected but `)' found
(1+2)*3
^
expr.apply for token 1 at position 1.2 offset 1 returns [1.5] parsed: EAdd(EConst(1),EConst(2))
term-parens.apply for token `(' at position 1.1 offset 0 returns [1.6] parsed: EAdd(EConst(1),EConst(2))
term.apply for token `(' at position 1.1 offset 0 returns [1.6] parsed: EAdd(EConst(1),EConst(2))
term.apply for token 3 at position 1.7 offset 6 returns [1.8] parsed: EConst(3)
plus.apply for token EOF at position 1.8 offset 7 returns [1.8] failure: ``+'' expected but EOF found
(1+2)*3
^
minus.apply for token EOF at position 1.8 offset 7 returns [1.8] failure: ``-'' expected but EOF found
(1+2)*3
^
expr.apply for token `(' at position 1.1 offset 0 returns [1.8] parsed: EMul(EAdd(EConst(1),EConst(2)),EConst(3))
Tree: EMul(EAdd(EConst(1),EConst(2)),EConst(3))
Eval: 9
scala> test(parens,"(1+2)")
term.apply for token 1 at position 1.2 offset 1 returns [1.3] parsed: EConst(1)
mul.apply for token `+' at position 1.3 offset 2 returns [1.3] failure: ``*'' expected but `+' found
(1+2)
^
div.apply for token `+' at position 1.3 offset 2 returns [1.3] failure: ``/'' expected but `+' found
(1+2)
^
add.apply for token `+' at position 1.3 offset 2 returns [1.4] parsed: +
term.apply for token 2 at position 1.4 offset 3 returns [1.5] parsed: EConst(2)
mul.apply for token `)' at position 1.5 offset 4 returns [1.5] failure: ``*'' expected but `)' found
(1+2)
^
div.apply for token `)' at position 1.5 offset 4 returns [1.5] failure: ``/'' expected but `)' found
(1+2)
^
add.apply for token `)' at position 1.5 offset 4 returns [1.5] failure: ``+'' expected but `)' found
(1+2)
^
sub.apply for token `)' at position 1.5 offset 4 returns [1.5] failure: ``-'' expected but `)' found
(1+2)
^
expr.apply for token 1 at position 1.2 offset 1 returns [1.5] parsed: EAdd(EConst(1),EConst(2))
Tree: EAdd(EConst(1),EConst(2))
Eval: 3
As you can see, even for these very short input strings
the output is pretty verbose.
It does, however, show you what token it is trying to parse
and where in the input stream that token is, so by paying attention
to the position and offset numbers you can see where it is backtracking.
When you have found the problem and are done debugging, you can remove
the DebugStandardTokenParsers class and take out all of the
!!! wrapping operations, or you can leave everything in place
and disable the wrapper output by changing the
definition of the implicit !!! operator to this:
def !! = p
Or, if you want to make it possible to enable debugging output later,
change !!! to return either p or
new Wrap(p) depending on some debugging configuration value.
Updated Example
Below is the complete program with all of the above changes.
import scala.util.parsing.combinator.syntactical.StandardTokenParsers
sealed abstract class Expr {
def eval():Int
}
case class EConst(value:Int) extends Expr {
def eval():Int = value
}
case class EAdd(left:Expr, right:Expr) extends Expr {
def eval():Int = left.eval + right.eval
}
case class ESub(left:Expr, right:Expr) extends Expr {
def eval():Int = left.eval - right.eval
}
case class EMul(left:Expr, right:Expr) extends Expr {
def eval():Int = left.eval * right.eval
}
case class EDiv(left:Expr, right:Expr) extends Expr {
def eval():Int = left.eval / right.eval
}
case class EUMinus(e:Expr) extends Expr {
def eval():Int = -e.eval
}
trait DebugStandardTokenParsers extends StandardTokenParsers {
class Wrap[+T](name:String,parser:Parser[T]) extends Parser[T] {
def apply(in: Input): ParseResult[T] = {
val first = in.first
val pos = in.pos
val offset = in.offset
val t = parser.apply(in)
println(name+".apply for token "+first+
" at position "+pos+" offset "+offset+" returns "+t)
t
}
}
implicit def toWrapped(name:String) = new {
def !! = new Wrap(name,p) //for debugging
//def !! = p //for production
}
}
object ExprParser extends DebugStandardTokenParsers {
lexical.delimiters ++= List("+","-","*","/","(",")")
def value = numericLit ^^ { s => EConst(s.toInt) }
def parens:Parser[Expr] = "(" ~> expr <~ ")"
def unaryMinus:Parser[EUMinus] = "-" ~> term ^^ { EUMinus(_) }
def term = "term" !!! ( value | "term-parens" !!! parens | unaryMinus )
def binaryOp(level:Int):Parser[((Expr,Expr)=>Expr)] = {
level match {
case 1 =>
"add" !!! "+" ^^^ { (a:Expr, b:Expr) => EAdd(a,b) } |
"sub" !!! "-" ^^^ { (a:Expr, b:Expr) => ESub(a,b) }
case 2 =>
"mul" !!! "*" ^^^ { (a:Expr, b:Expr) => EMul(a,b) } |
"div" !!! "/" ^^^ { (a:Expr, b:Expr) => EDiv(a,b) }
case _ => throw new RuntimeException("bad precedence level "+level)
}
}
val minPrec = 1
val maxPrec = 2
def binary(level:Int):Parser[Expr] =
if (level>maxPrec) term
else binary(level+1) * binaryOp(level)
def expr = "expr" !!! ( binary(minPrec) | term )
def parse(s:String) = {
val tokens = new lexical.Scanner(s)
phrase(expr)(tokens)
}
def parse(p:Parser[Expr], s:String) = {
val tokens = new lexical.Scanner(s)
phrase(p)(tokens)
}
def apply(s:String):Expr = {
parse(s) match {
case Success(tree, _) => tree
case e: NoSuccess =>
throw new IllegalArgumentException("Bad syntax: "+s)
}
}
def test(exprstr: String) =
printParseResult(parse(exprstr))
def test(p:Parser[Expr], exprstr: String) =
printParseResult(parse(p,exprstr))
def printParseResult(pr:ParseResult[Expr]) = {
pr match {
case Success(tree, _) =>
println("Tree: "+tree)
val v = tree.eval()
println("Eval: "+v)
case e: NoSuccess => Console.err.println(e)
}
}
//A main method for testing
def main(args: Array[String]) = test(args(0))
}
A scheduler that uses multiple worker threads
for continuations-based Scala coroutines.
In my recent series of posts that
ended with a complete Scala server
that uses continuations-based coroutines to store per-client state,
I asserted that the single-threaded scheduler implementation in that example
could relatively easily be replaced by a scheduler
that uses multiple threads.
In this post I provide a simple working example of such a
multithread scheduler.
We can use the standard
thread-pool
approach in which we have a pool
of worker threads that independently pull from a common task queue.
Java 1.5 introduced a set of classes and interfaces in the
java.util.concurrent package
to support various kinds of thread pools
or potentially other task scheduling mechanisms.
Rather than writing our own, we will use an
Executor
from that package.
We have an additional requirement that makes our situation a little bit
more complex than the typical thread-pool: our collection of tasks includes
both tasks that are ready to run and tasks that are currently blocked
but will become ready to run at some point in the future.
We will implement a new scheduler class JavaExecutorCoScheduler
that maintains a list of blocked tasks and
uses a Java Executor to manage runnable tasks.
The updated complete source code for this post is available
on github in my nioserver
project under the tag
blog-executor.
Managing Tasks
As mentioned above, we need to deal with two kinds of tasks:
tasks that are ready to run and tasks that are blocked.
The standard
Executor
class allows us to submit a task for execution, but does not handle
blocked tasks.
Since we don't want to submit blocked tasks to the Executor,
we have to queue them up ourselves.
We have two issues to attend to:
When our scheduler is passed a task, we must put it into our own
queue of blocked tasks if it is not currently ready to run.
When a previously blocked task becomes ready to run,
we must remove it from our queue of
blocked tasks and pass it to the Executor.
The first issue is straightforward, as our framework already allows us to
test the blocker for a task and see if the task is ready to run.
In order to properly take care of the second issue, we will make a small
change to our framework to allow us to notice when a blocker has probably
stopped blocking so that we can run the corresponding task.
We do this by modifying our CoScheduler class to add
a method to notify it that a blocker has probably become unblocked:
def unblocked(b:Blocker):Unit
We call this method from CoQueue in the two places where
we previously called scheduler.coNotify:
in the blockingEnqueue method after we have enqueued an item
to notify the scheduler that the dequeue side is probably unblocked,
and in the blockingDequeue method after we have dequeued an item
to notify the scheduler that the enqueue side is probably unblocked.
Those two methods in CoQueue now look like this:
def blockingEnqueue(x:A):Unit @suspendable = {
enqueueBlocker.waitUntilNotBlocked
enqueue(x)
scheduler.unblocked(dequeueBlocker)
}
def blockingDequeue():A @suspendable = {
dequeueBlocker.waitUntilNotBlocked
val x = dequeue
scheduler.unblocked(enqueueBlocker)
x
}
The implementation of unblocked in our default scheduler
DefaultCoScheduler is just a call to coNotify,
so the behavior of that system will remain the same as it was before we added
the calls to unblocked.
Because we need to ensure that all of our NIO read and write operations
are handled sequentially, we continue to manage those tasks separately
with our NioSelector class,
where all of the reads are executed on one thread and all of the writes
are executed on another thread.
Scheduler
We already have a scheduler framework that defines a CoScheduler
class as the parent class for our scheduler implementations,
which requires that we implement the methods
setRoutineContinuation, runNextUnblockedRoutine
and the newly added unblocked.
In our JavaExecutorCoSchduler,
our setRoutineContinuation method is responsible for storing
or executing the task.
It checks to see if the task is currently blocked, storing it
in our list of blocked tasks if so.
Otherwise, it passes it to the thread pool (which is managed by an
ExecutorService),
which takes care of managing the threads and running the task.
We define a simple case class, RunnableCont, to turn our task
into a Runnable that is usable by the pool.
Our unblocked method gets passed a blocker which is probably
now unblocked.
We test that, and if in fact it is still blocked we do nothing.
If it is unblocked, then we remove it from our list of blocked tasks
and pass it to the pool.
The runNextUnblockedRoutine method in this scheduler doesn't
actually do anything, since the pool is taking care of running everything.
We just return SomeRoutinesBlocked so that the caller goes
into a wait state.
In addition to the above three methods, we will have our thread pool,
a lock that we use when managing our blocked and runnable tasks,
and a set of blocked tasks waiting to become unblocked.
For this implementation we choose to use a thread pool of a fixed size,
thus the call to
Executors.newFixedThreadPool.
Here is our complete JavaExecutorCoScheduler class:
package net.jimmc.scoroutine
import java.lang.Runnable
import java.util.concurrent.Executors
import java.util.concurrent.ExecutorService
import scala.collection.mutable.LinkedHashMap
import scala.collection.mutable.SynchronizedMap
class JavaExecutorCoScheduler(numWorkers:Int) extends CoScheduler {
type Task = Option[Unit=>Unit]
case class RunnableCont(task:Task) extends Runnable {
def run() = task foreach { _() }
}
private val pool = Executors.newFixedThreadPool(numWorkers)
private val lock = new java.lang.Object
private val blockedTasks = new LinkedHashMap[Blocker,Task] with
SynchronizedMap[Blocker,Task]
private[scoroutine] def setRoutineContinuation(b:Blocker,task:Task) {
lock.synchronized {
if (b.isBlocked) {
blockedTasks(b) = task
} else {
pool.execute(RunnableCont(task))
coNotify
}
}
}
def unblocked(b:Blocker):Unit = {
lock.synchronized {
if (!b.isBlocked)
blockedTasks.remove(b) foreach { task =>
pool.execute(RunnableCont(task)) }
}
coNotify
}
def runNextUnblockedRoutine():RunStatus = SomeRoutinesBlocked
}
Synchronization
Although not necessitated by the above changes,
I added one more change to CoScheduler
to improve its synchronization behavior.
While exploring various multi-threading mechanisms as alternatives to
using Executor,
I wrote a scheduler called MultiThreadCoScheduler
in which I implemented my own thread pool
and in which the master thread directly
allocated tasks to the worker threads in the pool.
Although that scheduler was quite a bit larger than the one presented
above, it provided much more control over the threads, allowing me to
change the number of worker threads on the fly
and to be able to tell in my master
thread whether there were any running worker threads.
In MultiThreadCoScheduler,
the main thread would call coWait
to wait until it needed to wake up and hand out another task,
and the worker threads would call coNotify when they were
done processing a task and were ready to be assigned the next task.
Similarly, a call to coNotify would be issued whenever
a new task was placed into the task queue.
Unfortunately, Java's wait and
notify methods,
which are the calls underlying our coWait
and coNotify methods,
do not quite behave the way we would like.
If we compare those calls to the Java NIO
select and wakeup calls,
we note that if a call is made to wakeupbefore
a call to select,
the select call will return immediately.
The wait/notify calls do not behave this way;
if a call is made to notify when there is no thread waiting
in a wait call on that
monitor, the notify call
does nothing, and the following call to wait will wait until
the next call to notify.
This small difference in semantics actually makes a pretty big difference
in behavior, because it means when using wait and
notify you must be concerned with which happens first.
Let's see how that works.
In a typical scenario we have a resource with a boolean state that
indicates when a thread can access that resource,
for example, a queue with a boolean state of "has some data" that indicates when
a reader thread can pull an item from the queue (and perhaps another boolean
state of "queue is full" that indicates when a writer thread can put an item
into the queue).
In the case of MultiThreadCoScheduler
we have a task with a "ready" flag that tells us when we can
assign that task to a worker,
and a worker with an "idle" flag that tells us when we can
assign a task to that worker.
When a task becomes ready to run, we want a thread
(other than the master, since it may be waiting)
to add the task to our queue of
tasks and then notify the master that a task is available.
Meanwhile, when the master is looking for an available task to assign
to an idle worker, it will query to
see if a task is available, and if not it will then wait until one becomes
available.
The problem sequence would be if the master checks for available tasks,
finds none, then before the master executes its wait, the non-master puts
a ready task into the queue and issues a notify to the master.
The result of this sequence would be a ready task in the queue, but a
master waiting for a notify.
When all of the synchronization is done within a single class, you can
ensure that the above problem sequencing of operations does not happen
by arranging that the code that places a ready task into the queue and
notifies the master happens within one synchronized block,
and the code used by the master to query the queue for a ready task and
then to wait happens within one synchronized block on the same
monitor.
But when dealing with subclasses, we run into the
"inheritance anomaly"
(or "inheritance-synchronization anomaly").
The essence of this problem is that the base class provides a method
that is synchronized, but the subclass would like to include more
functionality within that synchronized block.
If, as is often the case, the subclass does not have access to the monitor
being used by the base class to control its synchronization,
there is no way for it to do this.
In our case, we can implement something that is sufficient for our
current needs by
making a small change to our coWait
and coNotify methods in CoScheduler
so that they behave in the same manner as
select and wakeup:
if a call to coNotify is made before a call to coWait,
the call to coWait will return immediately.
We do this by changing the implementation of coWait and
coNotify in CoScheduler from this:
With the above change to our base class, our subclass no longer needs to
be concerned about the problem sequence described above,
because the call to coWait will return immediately if there
was a call to coNotify since the most recent previous call
to coWait.
Words are tools that we use to
clarify our concepts, express our emotions and
persuade others to our positions.
We use those tools to craft mental models which we deliver to our listener.
The better the job we do with those tools,
the more effectively we can communicate our message.
The words we use every day are our basic tools.
Like screwdrivers and pliers, these words are simple but versatile,
performing adequately for most tasks.
Occasionally we might want to use a more esoteric word for
a specific task, as we might pull out a pair of
bent needle nose pliers
when that tool is just right for the job.
The better your selection of tools, the better job you can do at making
a beautiful and effective work.
In a pinch you can use a slot-head screwdriver to set a Phillips screw,
but you stand a higher chance of damaging the screw head and it is more
difficult to set it just right.
Similarly but more subtly, you may be able to use a Phillips
screwdriver to set a
Frearson screw, but you will be able to do
a better job if you have a Frearson driver.
Most of us will probably not need this level of distinction and can get
by with just a Phillips, or indeed perhaps with just a slot-head driver,
but if you want to be able to craft the best results over the widest
range of projects, having that Frearson screwdriver in your toolbox
will provide one more area in which you can do things better.
Swear words are the sledgehammers of our verbal toolbox.
Like a sledgehammer, a swear word can pack a lot of punch,
and like a sledgehammer it lacks precision.
Sometimes a sledgehammer is the right tool for the job:
when you need to smash a hole in something, one good whack with a
sledgehammer can be far more effective than trying to use pliers
and screwdrivers to do the same thing.
But for most of us, most of the time, that's not the job we are trying to do.
Most of the time we are more interested in making a neat hole, and
we should pull out the electric drill, or the hole saw, or even the
Sawzall to do the job; or we just need to tap in a small nail,
where a standard hammer would work nicely.
If we smash it with a sledgehammer, it's likely that we will then need
to spend a lot of time cleaning things up afterwards, which would probably
be more work than using one of the other tools in the first place.
Some people seem to have a very small toolbox
and are constantly swinging around that sledgehammer.
They use it for almost everything; rather than pulling out a
screwdriver to set a screw, they whack it with their sledgehammer.
To me, everything these people say seems like a pile of smashed rubble.
I doubt that's really the message they want to deliver.
Even a single use of a sledgehammer word can derail
any kind of nuance or subtlety,
and casual use will likely overwhelm everything else in the message.
So go ahead and use a sledgehammer when it is appropriate,
but do so deliberately and fully conscious of your intended result.
Make an effort to add a good assortment of tools to your toolbox,
understand what you are trying to accomplish,
learn to use the best tool for the job and use it well.
Unless otherwise specified in individual blog entries, all source code in this blog is Copyright by Jim McBeath, as of the posting date, under the GNU Lesser General Public License (LGPL), Version 3.
