parsing (bad) xml in scala

I’ve been using the pdftohtml tool recently to convert PDF document into a convenient XML form. Unfortunately, about 10% of the time, the output XML isn’t quite XML and can’t be parsed (normally it’s the result of some kind of HTML tag that’s been left to cause trouble).

Initially, I was just catching these errors and tossing the documents, but that was throwing out a lot of good with the bad. The tagsoup library provides an easy way around this — you can plug it into the normal Scala XML framework, and voil√†, all your parsing issues go away. (Well, you might end up with crazy mal-formed document trees, but it’s a lossy business).

It’s as simple as adding the tagsoup dependency:

"org.ccil.cowan.tagsoup" % "tagsoup" % "1.2.1"

and then changing from:

XML.loadString(myDocument)

to

  val parser = new org.ccil.cowan.tagsoup.jaxp.SAXFactoryImpl().newSAXParser()
  val adapter = new scala.xml.parsing.NoBindingFactoryAdapter
  adapter.loadXML(Source.fromString(stripDtd(document)), parser)

And that’s it! You’ve now gone from accepting correct XML to accepting damn-near anything. Others might be inclined to call this a bad thing, but at the same time, you have to work with what you’re given. And given the choice between some slightly funky XML and the pains of understanding PDF’s directly, I’ll take the quasi-XML anyday.

sending large messages

Somehow it took me a long time to find this, even though it’s listed in the Akka configuration reference quite plainly.

If you have messages with larger payload sizes – as in you see these kinds of TooLongFrameException errors:

Error[org.jboss.netty.handler.codec.frame.TooLongFrameException:Adjusted frame length exceeds 1048576: 1292205 - discarded
        at org.jboss.netty.handler.codec.frame.LengthFieldBasedFrameDecoder.fail(LengthFieldBasedFrameDecoder.java:441)

you can adjust the default maximum frame size from 1MB using the following config line:

akka {
    remote.netty.message-frame-size = 100 MiB
}

It would be really nice if the error message dumped out when a frame is overfilled mentioned this…

distributed workers with akka

I’ve been playing with the Akka framework for Scala recently, and have found it mostly enjoyable, despite a few kinks and quirks. I find it doesn’t take too much time for me to wrap my head around the usage, which implies that it must be very well written indeed :).

I did run into one issue recently with respect to remoting – I wanted to start a number of remote workers and have them bind on their local address, but the documentation and howto’s generally refer to running on a single machine. It turns out it’s fairly simple – just use an empty hostname in your application.conf:

akka.remote {
  transport = "akka.remote.netty.NettyRemoteTransport"
  netty {
    hostname = ""
    port = 9999
  }
}

Now your servers will bind to the *(0.0.0.0) address. When addressing them, you have to use the IP address directly, as unfortunately, they won’t respond to hostname based addresses – e.g:

      
val addr = "akka://[email protected]:9999/user/search-worker" // works
val addr = "
akka://[email protected]:9999/user/search-worker" // refuses messages

yet another start script plugin for sbt

My mental powers aren’t what they used to be, or at least that’s what I start feeling like when I try to use sbt for anything more then the compile step. It’s either breathtakingly brilliant or incredibly obfuscated, or both. I’m really not sure yet.

In any case, I wanted to generate scripts to launch a few simple tasks from my project. My solution, in case it’s useful

import sbt._
import Keys._

object GenerateScripts extends Plugin {
val scriptClasses = SettingKey[List[String]](
  "script-classes", "List of classes to generate start scripts for.")

val genScripts = TaskKey[Unit](
  "generate-scripts", "Generate start scripts."
)

val scriptTemplate = """
#!/bin/bash

CLASSPATH="%s"
MAINCLASS="%s"
java -cp $CLASSPATH $MAINCLASS

"""

def genScriptsTask = (streams, target, scriptClasses, fullClasspath in Runtime) map {
(stream, target, scripts, cp) => {
  val log = stream.log
  for (f <- scripts) {
    val scriptName = f.split('.').last
    val targetFile = (target / scriptName).asFile
    val classPath = cp.map(_.data).mkString(":")
    log.info("Generating script for %s".format(f))
    IO.write(targetFile, scriptTemplate.format(classPath, f))
    targetFile.setExecutable(true)
  }
}
}

override val settings = Seq(
  scriptClasses := List(),
  genScripts <<= genScriptsTask
)
 
}

Add this to your project/Build.scala, and add:

scriptClasses := List("a.b.foo", "b.c.bar")

to your build.sbt.

If someone would like to explain to me the difference between TaskKeys and Commands, as well as how to add this as a dependency of the compile step, I’d be much obliged.

experiences in serialization

The short of it: use Jerkson — you can easily serialize case classes:

case class Author(name : String) {}
case class Document(title : String, data : String, authors : List[Author]) {}
...
val encoded = Json.generate(doc)
val decoded = Json.parse[Document](encoded)
decoded should (equal(d))

I’ve been working some more with Scala, and found that I needed to serialize some data (I’m working with Hadoop).

Unfortunately, as with most things in life, I’ve been presented with all too many choices:

I first tried Avro, given that it’s part of the Hadoop project so I thought it would be the most seamless way of getting things workly.

Sadly, this was not to be. Avro generated classes do not support the Writable type for Hadoop, allowing them to be dropped in. Instead, you’re required to change all of your mappers/reducers to take in AvroKey/AvroValue wrapped items, and to set your output/input via the AvroInput/OutputFormats. This, while tedious, would be fine, except that I hit a Scala compiler bug when trying to get it all working.

My other thought was to simple convert the Avro object instances into strings myself, and then output strings from Hadoop. Hacky, but, hey it would work.

Except: After digging through the Avro documentation I couldn’t find a way of just turning my Avro structures into a serialized string. I could send them off to another server via an RPC, but dumping them to a file myself was out of the question. Sigh.

A note to serialization designers: please, please, please — give me an easy way to turn an object into a string.

I then started puttering around with the various JSON projects for Scala. Since there is no standard way of doing it, there are a lot of various cobbled together options that I had to try before finding out one that worked. Jerkson, despite the odd name, “just works”. I specify my objects as case classes, and magic, they can be serialized.

So now I’ve gone from outputting nice typed structures from Hadoop to just dumping strings and interpreting them myself. But I’m okay with that – it works.

Operator Overload

The last week I’ve been using Scala to work on a pet project of mine. It’s a relatively nice language, but one quirk (which I’ve also noticed in Haskell) is the extensive use of operator overloading.

For example, here’s a code completion pop-up:

I want to share a rule of thumb that’s useful for these situations:

  • Operators are functions
  • Functions should have useful names

If I’m operating on 2 integers, then +, *, /, etc. all have perfectly obvious interpretations. If I’m operating on a XML node then what do things like “/:\“, “\\“, and “\mean? And more importantly, is that meaning conveyed better then using an alternative such as ‘findAll’?

I hate to be curmudgeony, but there’s a point where I’d rather type ‘append’, then ‘+:=’.

the buddhist nature of swimming

I’ve been reading The Empty Mirror. It’s a fascinating little book about a Dutchman and a year he spent in a Japanese Zen monastery a few years after WWII. It’s a really quick read, and I recommend it – I just happened upon it in the local used bookstore, but I think it’s worth the Amazon price too.

The book, as expected focuses on the authors time in the monastery and his interactions with the monk, and the trials, stresses and achievement he gets out of the whole thing. Since I’ve also been swimming more frequently these days, it was natural for me to think about how the activities are somewhat related. In some sense, swimming is my form of meditation – it’s an activity where you can completely empty your mind. It’s especially true when you’re working hard and the pain from your muscles wipes everything else out.

I’ve never really done an extensive survey on this, but from personal experience, swimmers are pretty mellow people. Maybe it’s due to their extensive Buddhist training? I should arrange for a conference between some monks and swimmers to investigate more. But first I should probably practice meditating (or swimming) some more.

Review: Dark Silicon and the End of Multicore Scaling

Paper link: p365-esmaeilzadeh

Premise

Single core scaling stopped some number of years ago. But we’re okay, because we now have the “multi-core revolution” (I realllly hate that phrase). Or are we?

It turns out that another, very real wall is blocking future progress — power density. Already CPU designs strive mightily to shutdown or slowdown underutilized circuitry to save power. But we’re reaching the point where processors simply won’t ever be able to run “full-out”.

This paper explores the future of scaling by extrapolating based on a wide range of processors over time, and they find, rather compellingly, that we’re pretty much boned.

Details

The paper is pretty dense, but it boils down to the creation of a model parameterized by processor features:

  • number of cores
  • number of threads
  • CPU frequency
  • L1/L2/DRAM cache size, speed, miss rate
  • DRAM fetch width

and code features:

  • % code that is parallel
  • % read instructions

You can fit this model based on existing processors and their benchmark performance, as well as their power consumption and die area.

Once the model is created, now the fun starts — we can see how performance will scale with future process improvements (moving to 32, 22, 16…nm), or if we assume highly parallel code, we can see how to optimize our CPU design (lots of cores)!

The short of it

If we make optimistic assumptions for how power consumption drops with process scaling, we still end up with the sobering conclusion that we’re rapidly reaching the point where we won’t be able to power all of the parts of a chip. 128 cores aren’t as useful if we can’t keep them all running.

On the plus side, I can buy 1000 watt power supplies now, so I’m looking forward to my 16 processor, 16 core machine of the future. Welcome to the multiprocessor revolution!

fun with shared libraries — version GLIBC_2.14 not found

The shared library system for linux, especially when it comes to libc, is (choose one): archaic|complex|awesome. Today in trying to run some software on our local cluster, I encountered this lovely error:

/lib/x86_64-linux-gnu/libc.so.6: version `GLIBC_2.14' not found

Why was this occurring? For some reason, there was a version bump in the glibc for the memcpy instruction. How memcpy’s interface could possibly changed in a non-backward-compatible fashion, I don’t know. Still, since my local machine has a later libc then our cluster machines, I’m effectively boned.

There is a way around this, namely, I can ask the compiler to emit references to a specific, older version:

__asm__(".symver memcpy,[email protected]_2.2.5");

Unfortunately, this code has to appear before any other uses of memcpy! Rather then update a whole lot of code, I took advantage of the -include option for gcc. I simply created a file with my desired symbol override:

# gcc-preinclude.h 

__asm__(".symver memcpy,[email protected]_2.2.5");

and forced the build (here, autotools) to always include that before any other code:

./configure CC=gcc -include /path/to/gcc-preinclude.h ...

And away we go. A full rebuild and I’m back to a usable program again. Hurray!

Review: DThreads: Efficient Deterministic Multithreading

I’ve decided to try and be more pro-active about reading papers from the community. Since I tend to forget everything I read, it’s best I write down somewhere my thoughts for later reference — I’ve decided to post these reviews here in case they prove useful to others.

PDF of the paper

Overview:

This paper follows one of the latest fads in systems (NB: academics have fads just like fashionistas) — deterministic threading. The main idea behind all of these papers is to try and allow users to make use of multi-core/multi-threaded programming, but at the same time have it be deterministic. This is helpful as it ensures the behavior we see when testing is the same as what we see at runtime, and it also helps make it easier to recreate test failures.

This is a non-trivial problem, and it has a lot of work behind it already. The contribution with dthreads is that it, (a) claims high performance, and (b) provides a drop-in replacement for existing threads.

How does it work:

There’s a standard trick for d-threading, and DThreads uses it as well. It’s somewhat a kin to transactions in databases. First, split each thread into a separate world that can’t communicate with the other threads. Buffer all of the updates that would go to shared memory. Then, at a synchronization point (mutex lock, condition var, etc.), wait for all of the threads to finish their work, and then apply the shared memory changes in a deterministic fashion.

The DThreads way of handling this is to run each thread as a separate process. Whenever a commit point is reached, the processes determine which parts of memory they’ve changed, and commit them to shared memory at that time.

There are a number of things that need to be handled to make this all possible — you need to provide a deterministic malloc, you have to ensure threads are created and destroyed in a deterministic way, etc.

Why aren’t we using it today?

Two reasons, really.

Speed

DThreads is faster then previous work on the subject, but still can end up a lot slower then regular threading. This isn’t unexpected — you have to do more work, so you end up paying for it.

Correctness

DThreads, while being a drop-in replacement for pthreads, isn’t really a drop-in replacement for pthreads. Unfortunately for deterministic threading proponents, this type of code:

Thread 1:

while not done:
  sleep(0)

Thread 2:
... do some work ...
done = 1

where synchronization is handled outside the scope of the threading library is all too common in the wild. This forces the use of more expensive techniques then DThreads, which keeps determistic threading, for the moment, an academic exercise.

What did I think of the paper

It’s well written (which I expect of all SOSP papers), and presents a bunch of interesting tricks for improving performance and making things work. The fact that it requires all synchronization be performed through pthreads calls is on the face of it, reasonable, but sadly, it is far from realistic when it comes to running everyday applications.

Still, fun to read.