Tuesday, August 30, 2011

A quick detour through Grub and choosing default operating system

I'm going to do a quick detour to talk about grub.

Grub is the boot manager of choice for Linux systems, and the one installed by default by Ubuntu, among others. My desktop at home dual boots between Ubuntu and Windows (I have gaming needs, after all), and Windows is the default operating system, so my wife doesn't have to do anything.

Setting that default was not exactly trivial. The web abounds with instructions on how to choose the default, most of which refer to the previous version of grub. About the newer version, not so much information.

So, in the end I used Ubuntu's Startup Manager to set this up. By the way, can anyone explain to me why you use Startup Manager to choose which OS to boot, and Bootup Manager to choose which processes will start? Sorry, I digress...

That worked nicely until the day I upgraded the system, at which point a new entry was created, changing the relative position of the Windows boot. That was disagreeable, so I decided to take a closer look.

The configuration used by grub during boot is located at /boot/grub, in particular /boot/grub/grub.cfg. But you shouldn't edit this file directly -- it is generated from the scripts located at /etc/grub, plus configuration on /etc/default/grub. Usually, it is this latter file you should edit.

To change the default operating system, you edit /etc/default/grub, change the setting GRUB_DEFAULT, and then run update-grub. Alas, the Startup Manager will do all this for you, but there is one thing the Startup Manager doesn't do...

So, here's the trick. The GRUB_DEFAULT is usually set to a number, indicating the relative position of the entry you want, but it can also be set to a name! To see what the entry names are, you can do a "grep menuentry /boot/grub/grub.cfg" -- the names are the strings between single or double-quotes right after "menuentry". For example:


$ grep menuentry /boot/grub/grub.cfg
menuentry 'Ubuntu, with Linux 2.6.38-11-generic' --class ubuntu --class gnu-linux --class gnu --class os {
menuentry 'Ubuntu, with Linux 2.6.38-11-generic (recovery mode)' --class ubuntu --class gnu-linux --class gnu --class os {
menuentry 'Ubuntu, with Linux 2.6.38-10-generic' --class ubuntu --class gnu-linux --class gnu --class os {
menuentry 'Ubuntu, with Linux 2.6.38-10-generic (recovery mode)' --class ubuntu --class gnu-linux --class gnu --class os {
menuentry 'Ubuntu, with Linux 2.6.38-8-generic' --class ubuntu --class gnu-linux --class gnu --class os {
menuentry 'Ubuntu, with Linux 2.6.38-8-generic (recovery mode)' --class ubuntu --class gnu-linux --class gnu --class os {
menuentry "Memory test (memtest86+)" {
menuentry "Memory test (memtest86+, serial console 115200)" {

This also shows why Startup Manager uses numbers instead of names: so that the latest Linux is always chosen. This seems a poor choice for me, for anything except the first entry, but there you go.

Anyway, once you got the name, all you have to do is edit /etc/default/grub, change the setting GRUB_DEFAULT, so that it is set to the name of the entry you want (don't forget the quotes), and then run update-grub.

Tuesday, July 5, 2011

Build a binary tree from pre-order traversal and in-order traversal

This post comes from i has 1337 code by way of An Algorithm a Day. I'm really just posting this to show the power of Scala collections.

The idea is that you have two sequential representations of a tree: one for in-order traversal, and the order for pre-order traversal. Just one of these representations are not enough to reconstruct the tree, but the two of them, in the absence of duplicate elements, is. See the links above for an example.

The problem lends itself to recursive solutions, but there's some list manipulation required to build the input for the recursive steps. The key point of the algorithm is the realization that the first element of pre-order is the root, and every element to the left of said root in the in-order belongs to the left of the tree, and every element to the right belongs to the right of the tree. The rest is pretty trivial.

Even so, Scala makes the trivial, well, trivial. Here's the full code:

case class Tree[T](el: T, left: Option[Tree[T]], right: Option[Tree[T]])

def mkTree[T](preorder: List[T], inorder: List[T]): Option[Tree[T]] = preorder.headOption map { head =>
    val (left, _ :: right) = inorder span (head !=)
    Tree(head, 
         mkTree(preorder filter (left contains), left), 
         mkTree(preorder filter (right contains), right))
}

Note: I'm using List instead of Seq so that I can use the :: extractor.

Monday, June 27, 2011

A very quick guide to project creation on SBT 0.10.0

SBT 0.10.0 is out, and it is a very different beast at first. Aside from the need for retooling and relearning, it is a very big improvement.

However, these minor differences can slow down things a bit. For one thing, previous versions of SBT asked if you wanted to create a project if run on an empty directory, and that does not happen anymore. Now it creates some stuff automatically, but other stuff -- project name, version, scala version, directory layout -- it doesn't. So, let's take a quick look on how to accomplish (roughly) the same tasks.

In the example below, I named my SBT 0.10.0 script xsbt, so that I could use the older 0.7.7 with projects that are not yet migrated.

dcs@ayanami:~/github$ mkdir TestProject
dcs@ayanami:~/github$ cd TestProject
dcs@ayanami:~/github/TestProject$ xsbt
Getting net.java.dev.jna jna 3.2.3 ...
:: retrieving :: org.scala-tools.sbt#boot-app
 confs: [default]
 1 artifacts copied, 0 already retrieved (838kB/35ms)
Getting Scala 2.8.1 (for sbt)...
:: retrieving :: org.scala-tools.sbt#boot-scala
 confs: [default]
 4 artifacts copied, 0 already retrieved (15296kB/232ms)
Getting org.scala-tools.sbt sbt_2.8.1 0.10.0 ...
:: retrieving :: org.scala-tools.sbt#boot-app
 confs: [default]
 34 artifacts copied, 0 already retrieved (6012kB/215ms)
[info] Set current project to root (in build file:/home/dcs/.sbt/plugins/)
[info] Set current project to default (in build file:/home/dcs/github/TestProject/)
> set name := "TestProject"
[info] Reapplying settings...
[info] Set current project to default (in build file:/home/dcs/github/TestProject/)
> set version := "1.0"
[info] Reapplying settings...
[info] Set current project to default (in build file:/home/dcs/github/TestProject/)
> set scalaVersion := "2.9.0-1"
[info] Reapplying settings...
Getting Scala 2.9.0-1 ...
:: retrieving :: org.scala-tools.sbt#boot-scala
 confs: [default]
 4 artifacts copied, 0 already retrieved (20447kB/186ms)
[info] Set current project to default (in build file:/home/dcs/github/TestProject/)
> session save
[info] Reapplying settings...
[info] Set current project to default (in build file:/home/dcs/github/TestProject/)
> exit
dcs@ayanami:~/github/TestProject$ find . -type d
.
./project
./project/target
./project/target/config-classes
./project/target/scala_2.8.1
./project/boot
./project/boot/other
./project/boot/other/net.java.dev.jna
./project/boot/other/net.java.dev.jna/jna
./project/boot/other/net.java.dev.jna/jna/3.2.3
./project/boot/scala-2.9.0-1
./project/boot/scala-2.9.0-1/lib
./project/boot/scala-2.8.1
./project/boot/scala-2.8.1/lib
./project/boot/scala-2.8.1/org.scala-tools.sbt
./project/boot/scala-2.8.1/org.scala-tools.sbt/sbt
./project/boot/scala-2.8.1/org.scala-tools.sbt/sbt/0.10.0
./project/boot/scala-2.8.1/org.scala-tools.sbt/sbt/0.10.0/compiler-interface-bin_2.7.7.final
./project/boot/scala-2.8.1/org.scala-tools.sbt/sbt/0.10.0/compiler-interface-src
./project/boot/scala-2.8.1/org.scala-tools.sbt/sbt/0.10.0/compiler-interface-bin_2.9.0.final
./project/boot/scala-2.8.1/org.scala-tools.sbt/sbt/0.10.0/compiler-interface-bin_2.8.1.final
./project/boot/scala-2.8.1/org.scala-tools.sbt/sbt/0.10.0/xsbti
./target
./target/streams
./target/streams/$global
./target/streams/$global/$global
./target/streams/$global/$global/streams
./target/streams/$global/$global/streams/$global
dcs@ayanami:~/github/TestProject$ ls
build.sbt  project  target
dcs@ayanami:~/github/TestProject$ cat build.sbt


name := "TestProject"

version := "1.0"

scalaVersion := "2.9.0-1"

So far so good, but note that the directories for source are not created. The new version of SBT expects your IDE to do that (which is rather annoying for us vim users), or so it seems. However, the eclipse plugin can do that at the same time it creates the eclipse project. Here's an example:

dcs@ayanami:~/github/TestProject$ cat ~/.sbt/plugins/build.sbt 
resolvers += {
  val typesafeRepoUrl = new java.net.URL("http://repo.typesafe.com/typesafe/releases")
  val pattern = Patterns(false, "[organisation]/[module]/[sbtversion]/[revision]/[type]s/[module](-[classifier])-[revision].[ext]")
  Resolver.url("Typesafe Repository", typesafeRepoUrl)(pattern)
}

libraryDependencies <<= (libraryDependencies, sbtVersion) { (deps, version) => 
  deps :+ ("com.typesafe.sbteclipse" %% "sbteclipse" % "1.1" extra("sbtversion" -> version))
}
dcs@ayanami:~/github/TestProject$ xsbt
[info] Compiling 1 Scala source to /home/dcs/.sbt/plugins/project/target/scala_2.8.1/classes...
[info] Set current project to root (in build file:/home/dcs/.sbt/plugins/)
[info] Compiling 8 Scala sources to /home/dcs/.sbt/staging/a69240767cc8e721757e/target/scala-2.8.1.final/classes...
[info] Set current project to default (in build file:/home/dcs/github/TestProject/)
> eclipse create-src   
[info] Updating...
[info] Done updating.
[info] Successfully created Eclipse project files. Please select the appropriate Eclipse plugin for Scala 2.9.0-1!
> exit
dcs@ayanami:~/github/TestProject$ find . -type d
.
./project
./project/target
./project/target/config-classes
./project/target/scala_2.8.1
./project/boot
./project/boot/other
./project/boot/other/net.java.dev.jna
./project/boot/other/net.java.dev.jna/jna
./project/boot/other/net.java.dev.jna/jna/3.2.3
./project/boot/scala-2.9.0-1
./project/boot/scala-2.9.0-1/lib
./project/boot/scala-2.8.1
./project/boot/scala-2.8.1/lib
./project/boot/scala-2.8.1/org.scala-tools.sbt
./project/boot/scala-2.8.1/org.scala-tools.sbt/sbt
./project/boot/scala-2.8.1/org.scala-tools.sbt/sbt/0.10.0
./project/boot/scala-2.8.1/org.scala-tools.sbt/sbt/0.10.0/compiler-interface-bin_2.7.7.final
./project/boot/scala-2.8.1/org.scala-tools.sbt/sbt/0.10.0/compiler-interface-src
./project/boot/scala-2.8.1/org.scala-tools.sbt/sbt/0.10.0/compiler-interface-bin_2.9.0.final
./project/boot/scala-2.8.1/org.scala-tools.sbt/sbt/0.10.0/compiler-interface-bin_2.8.1.final
./project/boot/scala-2.8.1/org.scala-tools.sbt/sbt/0.10.0/xsbti
./target
./target/streams
./target/streams/$global
./target/streams/$global/ivy-sbt
./target/streams/$global/ivy-sbt/$global
./target/streams/$global/ivy-configuration
./target/streams/$global/ivy-configuration/$global
./target/streams/$global/update
./target/streams/$global/update/$global
./target/streams/$global/project-descriptors
./target/streams/$global/project-descriptors/$global
./target/streams/$global/$global
./target/streams/$global/$global/streams
./target/streams/$global/$global/streams/$global
./target/scala-2.9.0.1
./target/scala-2.9.0.1/cache
./target/scala-2.9.0.1/cache/update
./src
./src/main
./src/main/resources
./src/main/java
./src/main/scala
./src/test
./src/test/resources
./src/test/java
./src/test/scala

That's it! I strongly recommend reading the wiki linked at the beginning of this post, but this will get you going for small stuff.

Saturday, May 21, 2011

Scala 2.9 optimizes for comprehensions way better!

Ok, I completely missed this. For comprehensions in Scala 2.9 was way better optimized with the parameter -optimize than they were before! Take this code:

class OptEx {
    def sum(l: Array[Int]) = {
        var acc = 0
        for (i <- 0 until l.length) acc += l(i)
        acc
    }
}
This is the java bytecode generated with Scala 2.8.1 for the method sum:
public int sum(int[]);
  Code:
   0:   new     #7; //class scala/runtime/IntRef
   3:   dup
   4:   iconst_0
   5:   invokespecial   #12; //Method scala/runtime/IntRef."":(I)V
   8:   astore_2
   9:   new     #14; //class scala/runtime/RichInt
   12:  dup
   13:  iconst_0
   14:  invokespecial   #15; //Method scala/runtime/RichInt."":(I)V
   17:  aload_1
   18:  arraylength
   19:  invokevirtual   #19; //Method scala/runtime/RichInt.until:(I)Lscala/collection/immutable/Range$ByOne;
   22:  new     #21; //class OptEx$$anonfun$sum$1
   25:  dup
   26:  aload_0
   27:  aload_1
   28:  aload_2
   29:  invokespecial   #24; //Method OptEx$$anonfun$sum$1."":(LOptEx;[ILscala/runtime/IntRef;)V
   32:  invokeinterface #30,  2; //InterfaceMethod scala/collection/immutable/Range$ByOne.foreach$mVc$sp:(Lscala/Functio
n1;)V
   37:  aload_2
   38:  getfield        #34; //Field scala/runtime/IntRef.elem:I
   41:  ireturn
And this is what Scala 2.9.0 does:
public int sum(int[]);
  Code:
   0:   new     #7; //class scala/runtime/IntRef
   3:   dup
   4:   iconst_0
   5:   invokespecial   #12; //Method scala/runtime/IntRef."":(I)V
   8:   astore  6
   10:  new     #14; //class scala/runtime/RichInt
   13:  dup
   14:  iconst_0
   15:  invokespecial   #15; //Method scala/runtime/RichInt."":(I)V
   18:  aload_1
   19:  arraylength
   20:  istore_3
   21:  astore_2
   22:  getstatic       #21; //Field scala/collection/immutable/Range$.MODULE$:Lscala/collection/immutable/Range$;
   25:  aload_2
   26:  invokevirtual   #25; //Method scala/runtime/RichInt.self:()I
   29:  iload_3
   30:  invokevirtual   #29; //Method scala/collection/immutable/Range$.apply:(II)Lscala/collection/immutable/Range;
   33:  dup
   34:  astore  8
   36:  invokevirtual   #34; //Method scala/collection/immutable/Range.length:()I
   39:  iconst_0
   40:  if_icmple       83
   43:  aload   8
   45:  invokevirtual   #37; //Method scala/collection/immutable/Range.last:()I
   48:  istore  4
   50:  aload   8
   52:  invokevirtual   #40; //Method scala/collection/immutable/Range.start:()I
   55:  istore  9
   57:  iload   9
   59:  iload   4
   61:  if_icmpne       89
   64:  iload   9
   66:  istore  5
   68:  aload   6
   70:  aload   6
   72:  getfield        #44; //Field scala/runtime/IntRef.elem:I
   75:  aload_1
   76:  iload   5
   78:  iaload
   79:  iadd
   80:  putfield        #44; //Field scala/runtime/IntRef.elem:I
   83:  aload   6
   85:  getfield        #44; //Field scala/runtime/IntRef.elem:I
   88:  ireturn
   89:  iload   9
   91:  istore  7
   93:  aload   6
   95:  aload   6
   97:  getfield        #44; //Field scala/runtime/IntRef.elem:I
   100: aload_1
   101: iload   7
   103: iaload
   104: iadd
   105: putfield        #44; //Field scala/runtime/IntRef.elem:I
   108: iload   9
   110: aload   8
   112: invokevirtual   #47; //Method scala/collection/immutable/Range.step:()I
   115: iadd
   116: istore  9
   118: goto    57

Time to take your old benchmarks out of the closet, people!