Category Archives: software

Algorithms I: Notes in Week 5

Scattered thoughts:

A course on learning a programming language will help answer the question, “how do I do X?” The fun thing about an algorithms course is that the question is “how do I do X within certain parameters of time and space?”

In the real world, the two questions are actually one and the same. I’ve just come away from a project that had serious scalability problems, because many of its features could handle only very small sets of data used in development; when the app was run against live data, things stopped working because they would hit a timeout limit or processes would run out of memory.

I’m learning quickly that I can often intuit the “shape” of how an algorithm will perform, and I now have better language for describing this, but I’m not so good at calculating precisely the order of growth for even slightly complex code. It’s hard!

One paranoia-inducing aspect of programming assignments: for week 4’s assignment, a single timing test (1 out of 17) failed for my code because it took too long to finish. It’s hard to figure out… does this single failure expose a flaw in my overall implementation (if so, why did the other 16 pass)? Or was this last test thrown in as a “bonus” involving a difficult set of inputs that would require further optimization if you wanted to get full points? This is a tricky thing to assess as a student, and something only a human being would be able to tell you.

Trees are truly magical. I feel like I’ve barely started to grasp their many applications.

Algorithms I on Coursera

I’m currently taking the “Algorithms I” course on Coursera, a session of which started on January 22nd. I thought I’d write up my impressions so far on taking my first MOOC.

As someone who taught at a university for seven years in the humanities, I should say right off the bat that I dislike the idea of online learning for the reasons you might expect. But this course appealed to me for a few reasons. It’s developed and taught by Robert Sedgewick and Kevin Wayne, the authors of the highly regarded Algorithms, 4th Edition book. The syllabi of the two-course sequence on Coursera would make for the type of semester-length course you’d find in a respectable Computer Science department. Finally, Coursera has a reputation for offering more rigorous and demanding courses than other similar MOOC sites.

So far, I’m keeping up with the schedule and am in the middle of the Week 2 material. I’ve found it to be a positive experience so far, and more challenging than I’d expected!

Some initial impressions:

  • The course is a serious time commitment. Per week, it’s 2 hours of lecture + 2 hours for exercises + 4-12 hours for the programming assignment. I’ve chosen to skip the “interview questions” supplementary material.
  • Assignment grading is, thus far, very rigorous. Submitted source code is analyzed and run through a battery of tests measuring not only correctness, but code cleanliness, run times, and memory use, and scored accordingly.
  • The ability to submit exercises and assignments as many times as you like in order to improve your grade score is a fantastic feature. (I don’t know if all Coursera courses work this way.) It means you can really learn from your mistakes by correcting them; also, it gives you the chance to try out alternative solutions. This is WAY better than the traditional one-shot-only model of graded assignments, which is terrible for actual learning.
  • Basing the course on a published textbook (which is optional) is extremely helpful. There’s material covered more deeply in the text than in the lectures, but the lectures also address some aspects of topics and problems not covered in the book. This makes for a strong complementary relationship between the two; it doesn’t feel like the lectures are simply repeating the textbook.
  • You’re firmly expected to have some basic programming skills and a bit of math as a prerequisite. I like that the lectures keep the focus on the topics at hand, and don’t try to make the course all things to all people. If students need to “catch up” because they’re new to Java or their math is rusty, they use the discussion forums to do so.

As for the actual material, I’ve already learned a lot so far:

  • I’ve gotten some exposure to formal methods for algorithm analysis. A week and a half obviously isn’t going to make anyone great at this, but at least I now have some approaches for thinking through correctness, run times, and memory use mathematically, whereas before, I would mostly work empirically.
  • I can better identify different orders of growth and some of the common code patterns that indicate them.
  • The first week’s case study of different algorithms for Union-Find was, for me, a thought-provoking exercise in what is possible with arrays vs trees in representing relationships among data. The programming assignment is so stringent that it’s difficult to satisfy all the run time and memory requirements for a perfect score. This has generated a lot of insightful discussion in the forums about optimization.

Algorithms really get at the essence of what programming is. Anyone who works as a programmer has to put into practice algorithmic thinking to some degree, even if they aren’t aware of it.

I plan to continue writing about this as a way to keep me accountable for completing the two-course sequence.

A Major Update to refine_viaf

I’ve rewritten my refine_viaf project in Java. It’s what refine.codefork.com is now running. The old python code is considered deprecated and will no longer be maintained, but will remain available in the python-deprecated branch on github.

The only thing most users need to know is that refine_viaf should return better results now. For the curious, this post explains the subtle but important differences in the new version and some reasons for the rewrite.

Differences

In a nutshell, the main difference/improvement is that searches now behave more like the VIAF website.

This is due mainly to how sources (i.e. “LC” for Library of Congress) are handled. Previously, either the source specified on the URL or the “preferred source” from the config file was used to filter out search results, but it did NOT get passed into the actual VIAF search query. This could give you some weird results. The new version works like VIAF’s website: if you don’t specify a source, everything gets searched; if you do specify one, it DOES get passed to the VIAF search query. Simple.

The old version had weird rules for which name in each VIAF “cluster” result it actually displayed. In the new version, if you don’t specify a source, the most popular name (ie. the name used by the most sources) for a search result is used for display. If you specify a source, then its name is always used.

The old version supported a comma-separated list of sources at the end of the URL path. In the new version, only a single source is supported, since that’s what VIAF’s API accepts.

Lastly, the licenses are different: the python version was distributed under a BSD license. The new version is GNU GPL.

Other reasons for the rewrite

The changes above could have been implemented in python. I decided to rewrite it in Java for a few reasons:

– Overall performance is better in Java. The Django app used BeautifulSoup because VIAF’s XML used to be janky, but it appears this is no longer the case; Java’s SAX parser works great with their XML these days and is very fast. BeautifulSoup would leak memory and consume a lot of CPU, to the point where it would trigger automated warnings from my VPS provider. My server is very modest and needs to run other things, so these were real problems. Running the service as a single multi-threaded Java process keeps memory usage low and predictable, and it never spikes the CPU.

– Running a Java jar file is MUCH easier for people who want to run their own service, especially on Windows. With the python version, you had to install pip, install a bunch of packages, and create and configure a Django app, all of which put the software out of reach of many users who might want to run it.

– I don’t care what other people think: I like Java. Plus I wanted to experiment with Spring Boot. There are much leaner web frameworks I could have used to save some memory, but it was interesting to play with Spring.

Leave a comment!

If you use this thing, please take a second and leave a comment on this post. I’m interested to know how many people really run this on their own computers.

Enjoy.

A Year of Stats for refine.codefork.com

A year ago, I wrote an OpenRefine reconciliation service that queries VIAF and posted the source code on github. I’ve also been hosting it publicly at http://refine.codefork.com for anyone to use.

Below are two charts showing a year’s worth of usage statistics for this service. The first chart counts web requests made. (The way OpenRefine works, a single web request contains up to 10 name reconciliation queries. 200 web requests can translate to as many as 2000 name reconciliations.) The second chart counts the unique hosts (ie. unique computers, more or less) that used the service.

Last month, the busiest one yet, 47 different computers made an average of approximately 2360 name reconciliations each!

This usage has certainly exceeded my expectations. Now and then, I get a very nice tweet or two from someone who’s used it, which is really gratifying, considering it was just a little side project I threw together. You just never know.

Taking A Fresh Look at PHP

I’ve recently started working on a PHP/Laravel project.

PHP isn’t new to me. Many years ago, I wrote a very simple online catalog and shopping cart, from scratch, for a friend who had his own business as a rare book dealer. He used it with much success for several years. I’d also done a bit of hacking on some Drupal plugins.

Coming back to PHP now, I’m finding myself in a world MUCH different than the one I’d left.

First off, let’s admit that PHP comes with a lot of baggage. For a long time, “real” programmers shunned PHP because it was born as a language cobbled together to do simple web development but not much more. Its ease of use, combined with the fact that it was easy to deploy on commodity web hosting, meant you could find PHP talent for relatively cheap to build your applications. The stereotype was that PHP developers relied on a lot of patchy copy-and-paste solutions to build shoddy and insecure websites.

A LOT has happened since then. Here’s what I’ve encountered so far, diving back into PHP:

Object-orientation: PHP has had objects for a long time, but more recent features like namespaces, traits, and class autoloading have made newer PHP projects very strongly object-oriented. You can even find books on design patterns for PHP.

To me, this is the single most important positive change to the PHP world. The culture has changed from an ad hoc procedural mindset to more sophisticated thinking about coding for large-scale architectures.

Frameworks: Several major MVC frameworks exist, many of them drawing inspiration from Rails.

Performance: As of 5.5, PHP has a built-in opcode cache, making it much more performant. An alternative to core PHP is the HHVM project, backed by Facebook, which is a high-performance PHP implementation. HHVM has had a “rising tide” effect: the forthcoming PHP7 is supposed to be as fast as HHVM. So whatever you use, you can expect good performance at scale.

Tooling: There is sophisticated tooling like composer and a vibrant ecosystem of packages. While you can still deploy PHP applications the old way, using Apache and mod_php, there is a mature FastCGI Process Manager (PHP-FPM) engine that isolates PHP processes from the web server. PHP-FPM allows Apache/nginx/whatever web server to handle static content while a pool of processes handles PHP requests. This results in much more efficient memory usage and better performance.

Success: Many respectable, high-profile products have been built using PHP: WordPress, Drupal, and Facebook, just to name a few.

But all this is just to state a bunch of known facts. To me, the biggest suprise has been in the EXPERIENCE of beginning to write code again in PHP and using Laravel: what does that FEEL like?

In a word, it feels like Java, minus the strong typing. This is an entirely good thing in my opinion, despite criticisms that PHP technologies have become too complex and overdesigned.

The biggest paradigm difference between PHP and other popular web application back-ends is that nothing remains loaded in memory between requests. It’s true that opcode caching means PHP doesn’t have to re-compile PHP source code files to opcodes every time, which speeds things up greatly, but the opcodes still need to be executed for each request, from bootstrapping the application to finishing the HTTP response. In practice, this doesn’t actually matter, but it’s such a significant under-the-hood difference from, say, Django and Rails, that I find myself thinking about it from time to time.

It’s reassuring that when I scour the interwebs researching something PHP-related, I’m finding a lot of informed technical discussions and smart people who have come to PHP from other languages and backgrounds. It bodes well for the strengths and the future of the technology.

On Magic

Kids, I hate to break it to you, but there is no such thing as magic.

The cool whizzy stuff on your screen that impresses you: that’s the result of work. The button that was broken yesterday, that now works correctly today: also the product of work. The screen that was discussed in a meeting last week that suddenly appeared today on the development server: yup, work. When you look for a feature in the web application and it isn’t there, there’s this thing that can create it and put it there: it’s called work.

Someday we’ll all get over the mystifying aura of technology. Someday people will learn to recognize that programmers are not magicians, just workers, and that the work they do involves mundane, non-magical tasks, like wrestling with code libraries and frameworks to get them to do what we want, reorganizing files to make sure stuff exists in sensible places, and figuring out what to do when changing one piece affects three other pieces in unexpected ways.

And this means, someday, people will understand that, like any other kind of work, software development takes resources (namely, time!), not a magic wand. And no amount of “ambition” (read: wishful thinking) can really change that basic equation. You can pretend magic exists, but that doesn’t make it so. You aren’t fooling anyone. You just look childish.

When software development is recognized as work, there can be clarity about what is possible with a given set of resources. Then tasks can be sanely identified, specified, prioritized, coordinated, scheduled, executed, completed.

And then some really cool things can happen. Not magical things, but really cool things. Great things, even. The kind of great things that result from understanding, dedication, and hard work.

Adventures in Docker

large_h-trans

After you’ve taken the time to puzzle through what it is exactly, Docker is nothing short of life changing.

In a nutshell, Docker lets you run programs in separate “containers”, isolating the dependencies each one requires. This is similar to virtualization solutions like VMWare and Virtualbox but Docker is a much more fine grained, customizable tool that operates at a different level.

It took me a week of experimentation to develop a firm grasp of the Docker concepts and how all its pieces work together in practice. I’m now using it at work for development, and I hope to be setting up a configuration for staging soon.

This is a short write-up of what I’ve learned so far.

The Concepts

On a first glance, almost everyone (including me) mistakes Docker as another virtualization technology. It’s not. Virtualization lets you run a machine within a machine. A Docker container is more subtle: it segments or isolates part of your existing Linux operating system.

A container consists of a separate memory space and filesystem (taken from something called an image). A container actually uses the same kernel as your “host” system. Some fancy Linux kernel technologies allow all of this to happen; there is no hardware virtualization going on.

You start using Docker by creating an image or using an existing one made by someone else. An image is a filesystem snapshot. You can build images in an automated fashion using a Dockerfile, which allows you to “script” the running of commands to do things like install software and copy files around.

When you launch a container, Docker makes a “copy” of an image (well, not really, but we’ll pretend for now) and uses that to start a process. The fact that the filesystem is a “copy” is important: if you launch 2 containers using the same image, and the processes in each modify files, those changes happen in each CONTAINER’s filesystem; the image doesn’t change. Processes inside containers only see what’s in the container, so they are isolated from one another. This allows complete dependency separation, at the level of processes.

You can do a lot with containers. You can run multiple processes in them (though this is discouraged). You can start another process in an already running container, so it can interact with the already running process. After a container has stopped (by halting the process running in it), you can start it back up again. Again, any file changes made are in the container’s filesystem; the image remains unchanged.

Issues

There are three issues I’ve personally encountered so far in using Docker:

1) Persistent Storage

Containers are meant to be transient. In a well designed setup, you should, theoretically, be able to spin up new containers and discard old ones all the time, and not lose any data. This means that your persistent storage has to live somewhere else, in one of two places: a special “data container” or a directory mounted from the host filesystem.

Data containers were too complicated and weird, and I couldn’t get them to work the way I expected, so I mounted directories instead. This has the nice side effect that, as Dockerized processes change files, you can see those changes immediately from the host without having to do anything special to access them. I’m not sure, however, what “best practices” are concerning storage.

2) Multi-Container Applications

Many modern applications consist of several processes or require other applications. For example, my project at work consists of a Rails web app, a delayed_job worker process, an Apache Solr instance, and a MySQL database.

Since Docker strongly recommends a one-process-per-container configuration, you need a way to coordinate a set of running processes and make sure they can communicate with one another. Docker Compose does this, allowing you to easily specify whether containers should be able to open connections to each other’s network ports, share filesystems, etc.

Currently, Docker Compose is not yet considered “production ready.” While it addresses the need to orchestrate processes, there is also the problem of monitoring and restarting processes as needed. It’s not clear to me yet what the best tool is for doing this (it may even be a completely orthogonal concern to what Docker does).

3) Running Commands

Sometimes you need to use the Rails CLI to do things like run database migrations or a rake task. Running commands takes a bit of extra effort, since they need to happen in a container. A slight complication is whether to run the command in the existing Rails container or to start another one entirely for that new process. It’s a bit of typing, which is annoying.

The Payoffs

How is Docker life changing? There are several scenarios I encounter ALL THE TIME that Docker helps tremendously with.

* On the same machine, you can run several web applications, which each require different versions of, say, Ruby, Rails, MySQL and Apache, without dealing with software conflicts and incompatibilities.

* Related to the previous point, Docker lets you more easily experiment with different software without polluting your base system with a lot of crap you might never use again.

* There is MUCH less overhead and less wasted memory usage than with virtualization. If you allocate 1GB of RAM to a virtual machine but only use 512MB, the other half goes to waste. Docker containers only use as much memory as the processes themselves take up, plus a small bit of overhead. Since Docker uses unionfs to “copy” (really, overlay) images to container filesystems, the actual disk space used isn’t as much as you might think.

* Since Docker containers are entirely self-contained, they can be deployed in development, staging, and production environments with almost NO differences among them, thereby minimizing the problems that usually arise.

For me, a lot of the benefits boil down to this: virtualization is amazing, but in practice, I don’t use it that much because it’s too heavyweight and too coarse for my needs. A Virtualbox is a whole other machine that I need to think about. By working at the level of Linux processes, Docker is exactly the right kind of tool for managing application dependencies.

A cautionary note: there’s a lot of buzz right now around containers, including efforts at defining vendor-neutral standards, such as appc. Although Docker releases have been rapid and it is already seeing a lot of adoption, it feels bleeding edge to me. It’s exciting but in a few years, it’s entirely possible that another container solution might surpass it to become the de facto standard. The playing field is just too new, which means Docker comes with some risk. But it’s well worth exploring at this early stage, even if only to get a taste of the new ideas shaping systems configuration and deployment that are definitely here to stay.

Software Old and New

Waaaay back in middle school, I used WordPerfect 5.1 to type up book reports and other homework assignments. This was on a Tandy 1000, one of the first home computers. Having never used a PC before, much less word processing software, it took some time to learn. WordPerfect came with a plastic template you laid above the keyboard’s F-keys, which told you what pressing various key combinations did. In my ignorance, I hit Enter twice at the end of every line of text to get double line spacing, which, of course, made editing and revising a nightmare. My uncle, a computer wiz, laughed when he saw this, and taught me how to set the line spacing the right way. It amazed me that the computer could reflow the text automatically.

A lesson I learned from this was that the manual that came with the 3.5″ disks was pretty darn useful.

Back then, in the late 80s and early 90s, software was a specialized tool or instrument. I was fortunate to have a computer at home. Not everyone did. To use it proficiently, you had to do some learning. This was expected. It wasn’t WordPerfect’s fault that I didn’t even know line spacing existed as a feature. Like learning any powerful tool, it required some time and effort to develop the skills.

There’s been a drastic paradigm shift over the last 25 years. Software has become ubiquitous. It’s no longer just the programs you run on your home or work computer. It’s on our phones and tablets. It’s what web applications are made of. It’s in cars, ATMs, information kiosks, and home appliances. Commercial software rarely comes with user manuals anymore. My smartphone came with a single sheet of paper showing you how to turn it on. When there are Android updates, I don’t get a book that explains the additional gestures it now recognizes, what the new icons mean, or how the menus have been restructured. I’m expected to just poke around the new interface until I can do what I’m trying to do. When you visit a new website you haven’t been to before, you are similarly expected to already know how to navigate it. This is possible because there are common conventions around software features and interface design, so that, when using a new piece of software, you are not starting completely from scratch.

The consequence of this radical shift is that if you can’t immediately use a new piece of software, there are 2 possible explanations: 1) you are lacking a general “digital literacy” which most people are understood to have (as opposed to specialized knowledge), or 2) the software is crappy.

We take pity on digital illiterates, but we have no sympathy or patience for crappy software. “Why does it take me 3 clicks to get to X? Why doesn’t this application do Y? Why doesn’t the icon resemble this, instead of that?” These complaints are commonplace. Increasingly, it doesn’t seem to matter what the software actually does or what the level of its inherent complexity might be. The pace of technological change and the pressures of high-tech business have made it important for users to be able to use software immediately, and to be satisfied enough that they don’t run off to a competitor’s product. Our intolerance is a direct result of this frenzied climate, which has taken user-friendliness to the extreme of trying to be all things to all people (or at least, as many things to as many people as possible).

The problem is that there is a lot of variability in user preferences, opinions, and needs. The more that software tries to accommodate a wide variety of these concerns, the less useful it becomes as a tool. I think you see this especially in many mobile apps and websites. They DO very little, but they go out of their way to make it easy to do it. This focus on ease is deceptive. It leads to a false sense of empowerment. We are surrounded by software everywhere that appears to enable us to do all sorts of things, but we actually don’t understand enough to know how to operate things skillfully. We just click and swipe, click and swipe, and get frustrated when magic doesn’t happen.

Using technology as a tool can save significant work and allow us to do things not possible before. But that doesn’t necessarily imply that it is or should be easy. It’s a subtle but important difference. Knowing how to fly an airplane enables you to traverse thousands of miles in a few hours, but that doesn’t mean operating one is easy, or that should be. One should be trained to be a skilled pilot, so that she can make the machine do all the complex things it needs to, in a variety of situations. One shouldn’t expect a cockpit that lets anyone to marginally be able to fly a plane. Because how far is that going to get you, really?

Where To Find Info When Packages Break in Debian Testing

The chromium package in Debian testing broke a few days ago. After I ran “apt-get update” and “apt-get upgrade”, chromium disappeared from my Xfce menu, and the executable was gone from my system. Nothing like that has ever happened to me before. Odd!

When I tried to re-install it by running “apt-get install chromium”, I got the following error:

The following packages have unmet dependencies:
chromium : Depends: libudev0 (>= 146) but it is not installable
E: Unable to correct problems, you have held broken packages.

Indeed, there is no package called libudev0 (there is, however, a libudev1, which I already had installed). Mysterious.

Being fairly new to Debian testing, I was at a loss as to what to do. After some googling, I discovered some information that’s useful to users trying to troubleshoot broken packages.

I already knew that Debian has a searchable package database on their website. If you search for ‘chromium’ in the testing distribution, you’ll get to a page for it.

What I’d never noticed before were the links on the right-hand side. Every package apparently has its own mailing list archive and QA page.

The QA page isn’t the easily thing in the world to make sense of. I couldn’t find a simple listing of bugs in reverse chronological order, which would let me quickly see the newest bugs filed. The closest thing is the list of all open bugs. There is also a dashboard page which is vaguely reverse chronological, though it may be sorted by priority; it’s not clear.

In any event, this was good enough. I could see the bug for the error message I was getting. Turns out an update had mistakenly built the package for stable, which is why the unmet dependency was coming up.

It’s yet to be fixed, but at least now I know exactly what the problem is.

What Django Can (and Can’t) Do for You

I’m joining a team at work for the next few weeks to hammer out what will be my second significant Django project.

I’m not an expert on Django, but I have enough experience with it now to say that it facilitates the vast majority of web application programming tasks with very little pain. It’s highly opinionated and very complex, and has all the issues that come with that, but if you learn its philosophy, it serves you extremely well. And in cases where it doesn’t—say, with database queries that can’t be written easily with the Django ORM—you can selectively bypass parts of the framework and just do it yourself.

So I’ve been puzzled by complaints I’ve been hearing about how difficult it is to work with Django. There’s an initial learning curve, sure, but I didn’t think it was THAT bad. Yet over and over again, I kept hearing the grumbling, “why do I have to do it this way?”

A recent example came up with the way that Django does model inheritance. There’s a few ways to do it, with important differences in how the database tables are organized. You have to understand this in order to make a good choice, so of course, it takes a little time to research.

Having worked with Java’s Hibernate, I recognized some of the similarities in Django’s approach to addressing the fundamental problem of the impedance mismatch between object classes and database tables. Every ORM must deal with this, and there are nicer and less nice ways to deal with it. The point is, there’s no way to avoid it.

I realized that the complaints weren’t actually about Django per se, despite appearances. They were complaints about not understanding the underlying technologies. People were expecting Django to replace the need for knowledge about databases, HTTP, HTML, MVC architecture, etc. It doesn’t. That’s a poor way to approach what Django can do for you.

The metaphor of tools is useful here. If you gave me a set of sophisticated, high-quality tools to build a house, but I didn’t know the first thing about construction, I might complain that the tools suck because I can’t easily accomplish what I want, because I’m forced to use them in (what seems to me to be) clumsy ways. But that would be terribly misguided.

So the complaints weren’t about the merits of Django compared to how other frameworks do things. What they’re really saying is, “This is different from how I would do it, if I were writing a web framework from scratch.” Which is funny, because I’m not convinced they could invent a better wheel, given their limited knowledge and experience. (This is not a dig: I’ve worked on quite a few projects, many with custom frameworks, and doubt I could conceive of something easier to use and still as powerful as Django. Designing frameworks is hard.) Sometimes the complaints are thinly veiled anti-framework rants, which is fine, I suppose, if you prefer the good old days of 1998. But God help you if you try to create anything really complicated or useful.