O(n log n) isn’t bad

Posted on Thu 19 October 2017 in Programming • Tagged with algorithms, complexity, Big OLeave a comment

Most programmers should be familiar with the Big O notation of computational complexity. This is how, in very theoretical terms, we are describing the relative differences in the performance of algorithms.

Excluding the case of constant time complexity (O(1)), the vast majority of practical algorithms falls into one of the following classes:

  • O(log n)
  • O(n)
  • O(n log n)
  • O(n²)

The further down a class is on this list, the worse (less efficient) it gets. What may not be completely obvious, however, is the magnitude of differences.

Let’s have a closer look.

The best and the worst

First, it’s pretty easy when it comes to the extreme points. A logarithmic complexity is clearly great, because the number of operations barely even grows as the size of input increases. For N of one million, the (natural1) logarithm is equal to about 14. For one trillion — million times more — log n is only 27!

Such amazing scalability is one of the reasons why databases, for example, can execute queries extremely efficiently even for millions or billions of records.

On the other end, an algorithm that has quadratic complexity will only do well for very small datasets. It can still be useful in practice, especially as a small-input optimization of some larger procedure2, or because of some other desirable properties (like good parallelizability).

Outside of those carefully selected cases, however, the computational requirements of O(n²) for any large dataset are usually too great.

Middle ground

As for the remaining two classes, the linear one (O(n)) is probably the easiest to reason about.

In a linear algorithm, the number of operations increases steadily along with the size of input.
For thousand elements, you need roughly a thousand steps (times a constant factor).
For a million, there will be a million operations necessary.

Thus, by itself, the linear scaling doesn’t get any better or worse when data gets bigger3. In many cases, it means there is nothing to be exploited in the structure of input set that could make the running time any better (compared to e.g. the reliance of logarithmic searches on sorted order). Typically, all the data must be traversed at least once in its entirety.

All in all, it can be a decent time complexity, but it’s nothing to write home about.

A function has no name

What about O(n log n), then? It falls between the linear and the quadratic, which suggests that it’s somewhere half-way between mediocre and awful. We don’t even have a widely used word for it, meaning it is probably not even that important.

Both of those suppositions are wrong.

First, O(n log n) isn’t even remotely close to the “median” (whatever that means) of O(n) and O(n²). In reality, its asymptotic rate of growth places it very close to the former. You can see this pretty clearly by looking at the following plot:

Time complexity plot
Source

The gap between O(n) and O(n log n) barely even widens, even as the values on vertical axis increase to the limits of practicality.

Indeed, the log n part of the function grows slowly enough that, for many practical purposes, it can be considered a large “constant” in the complexity formula. Some complicated algorithm that’s technically linear may therefore be a worse choice than a simpler solution with O(n log n) scaling.

Sorting it out

What are the typical situations where O(n log n) arises in practice? Very often, it has to do with establishing some kind of ordering of the input which includes at least one of the following:

  • a wholesale sorting of it (using pairwise comparison)
  • repeated queries for the current maximum or minimum (via a priority queue)

Considering that many practical algoithms — from pathfinding to compression — utilize some form of sorting or sorted data structures, it makes O(n log n) quite an important complexity class.


  1. Natural logarithm has a base of e = 2.71828183… The exact choice of logarithm base doesn’t matter for asymptotic complexity, because it changes only the constant coefficient in the O(f(n)) function. 

  2. A widely used example is Timsort which switches from merge sort (O(log n)) to insertion sort (O(n²)) when the array slice is short enough to warrant it. 

  3. In reality, practical factors like memory/cache size, OS scheduling behavior, and a myriad of other things can make the actual running time scale sublinearly beyond a certain point. 

Continue reading

Rust as a gateway drug to Haskell

Posted on Tue 13 June 2017 in Programming • Tagged with Rust, Haskell, traits, typeclasses, monads, ADTs, FPLeave a comment

For work-related reasons, I had to recently get up to speed on programming in Haskell.

Before that, I had very little actual experience with the language, clocking probably at less than a thousand lines of working code over a couple of years. Nothing impressive either: some wrapper script here, some experimental rewrite there…

These days, I heard, there are a few resources for learning Haskell1 that don’t require having a PhD in category theory2. They may be quite helpful when your exposure to the functional programming is limited. In my case, however, the one thing that really enabled me to become (somewhat) productive was not even related to Haskell at all.

It was Rust.

In theory, this shouldn’t really make much of a sense. If you compare both languages by putting checkmarks in a feature chart, you won’t find them to have much in common.

Some of the obvious differences include:

  • predominantly functional vs. mostly imperative
  • garbage collection vs. explicit memory management
  • lazy vs. eager evaluation
  • rich runtime3 vs. almost no runtime
  • global vs. localized type inference
  • indentation vs. braces
  • two decades (!) vs. barely two years since release

Setting aside syntax, most of those differences are pretty significant.

You probably wouldn’t use Haskell for embedded programming, for instance, both for performance (GC) and memory usage reasons (laziness). Similarly, Rust’s ownership system can be too much of a hassle for high level code that isn’t subject to real time requirements.

But if you look a little deeper, beyond just the surface descriptions of both languages, you can find plenty of concepts they share.

Traits: they are typeclasses, essentially

Take Haskell’s typeclasses, for example — the cornerstone of its rich and expressive type system.

A typeclass is, simply speaking, a list of capabilities: it defines what a type can do. There exist analogs of typeclasses in most programming languages, but they are normally called interfaces or protocols, and remain closely tied to the object-oriented paradigm.

Not so in Haskell.

Or in Rust for that matter, where the equivalent concept exists under the name of traits. What typeclasses and traits have in common is that they’re used for all kinds of polymorphism in their respective languages.

Generics

For example, let’s consider parametrized types, sometimes also referred to as templates (C++) or generics (C#).

In many cases, a generic function or type requires its type arguments to exhibit certain characteristics. In some languages (like the legacy C++), this is checked only implicitly: as long as the template type-checks after its expansion, everything is okay:

template <typename T> T min(T a, T b) {
    return a > b ? b : a;
}

struct Foo {};

int main() {
    min(1, 2);  // OK
    min(Foo(), Foo());  // ERROR, no operator `>`
}

More advanced type systems, however, allow to specify the generic constraints explicitly. This is the case in Rust:

fn min<T: Ord>(a: T, b: T) -> T {
    if a > b { b } else { a }
}

as well as in Haskell:

min :: (Ord a) => a -> a -> a
min a b = if a > b then b else a

In both languages, the notion of a type supporting certain operations (like comparison/ordering) is represented as its own, first-class concept: a trait (Rust) or a typeclass (Haskell). Since the compiler is aware of those constraints, it can verify that the min function is used correctly even before it tries to generate code for a specific substitution of T.

Dynamic dispatch

On the other hand, let’s look at runtime polymorphism: the one that OO languages implement through abstract base classes and virtual methods. It’s the tool of choice if you need a container of objects of different types, which nevertheless all expose the same interface.

To offer it, Rust has trait objects, and they work pretty much exactly like base class pointers/references from Java, C++, or C#.

// Trait definition
trait Draw {
    fn draw(&self);
}

// Data type implementing the trait
struct Circle { radius: i32 }
impl Draw for Circle {
    fn draw(&self) { /* omitted */ }
}

// Usage
fn draw_all(objects: &Vec<Box<Draw>>) {
    for &obj in objects {
        obj.draw();
    }
}

The Haskell analogue is, in turn, based on typeclasses, though the specifics can be a little bit trickier:

{-# LANGUAGE ExistentialQuantification #-}

-- Typeclass definition
class Draw a where
    draw :: a -> IO ()

-- Polymorphic wrapper type
data Draw' = forall a. Draw a => Draw' a
instance Draw Draw' where
    draw (Draw' d) = draw d

-- Data types instantiating ("implementing") the typeclass
data Circle = Circle ()
instance Draw Circle where draw = undefined -- omitted
data Square = Square ()
instance Draw Square where draw = undefined -- omitted

-- Usage
drawAll :: (Draw a) => [a] -> IO ()
drawAll ds = mapM_ draw ds

main = do
    let shapes = [Draw' Circle (), Draw' Square ()]
    drawAll shapes

Here, the generic function can use typeclass constraints directly ((Draw a) => ...), but creating a container of different object types requires a polymorphic wrapper4.

Differences

All those similarities do not mean that Rust traits and Haskell typeclasses are one and the same. There are, in fact, quite a few differences, owing mostly to the fact that Haskell’s type system is more expressive:

  • Rust lacks higher kinded types, making certain abstractions impossible to encode as traits. It is possible, however, to implement a trait for infinitely many types at once if the implementation itself is generic (like here).

  • When defining a trait in Rust, you can ask implementors to provide some auxiliary, associated types in addition to just methods5. A similar mechanism in Haskell is expanded into type families, and requires enabling a GHC extension.

  • While typeclasses in Haskell can be implemented for multiple types simultaneously via a GHC extension, Rust’s take on this feature is to make traits themselves generic (e.g. trait Foo<T>). The end result is roughly similar; however, the “main implementing type” (one after for in impl ... for ...) is still a method receiver (self), just like in OO languages.

  • Rust enforces coherence rules on trait implementations. The topic is actually rather complicated, but the gist is about local (current package) vs. remote (other packages / standard library) traits and types.
    Without too much detail, coherence demands that there be a local type or trait somewhere in the impl ... for ... construct. Haskell doesn’t have this limitation, although it is recommended not to take advantage of this.

The M-word

Another area of overlap between Haskell and Rust exists in the data model utilized by those languages. Both are taking heavy advantage of algebraic data types (ADT), including the ability to define both product types (“regular” structs and records) as well as sum types (tagged unions).

Maybe you’d like Some(T)?

Even more interestingly, code in both languages makes extensive use of the two most basic ADTs:

  • Option (Rust) or Maybe (Haskell) — for denoting a presence or absence of a value
  • Result (Rust) or Either (Haskell) — for representing the alternative of “correct” and “erroneous” value

These aren’t just simple datatypes. They are deeply interwoven into the basic semantics of both languages, not to mention their standard libraries and community-provided packages.

The Option/Maybe type, for example, is the alternative to nullable references: something that’s been heavily criticized for making programs prone to unexpected NullReferenceExceptions. The idea behind both of those types is to make actual values impossible to confuse with nulls by encoding the potential nullability into the type system:

enum Option<T> { Some(T), None }
data Maybe a = Just a | Nothing

Result and Either, on the other hand, can be thought as an extension of this idea. They also represent two possibilities, but the “wrong” one isn’t just None or Nothing — it has some more information associated with it:

enum Result<T, E> { Ok(T), Err(E) }
data Either e a = Left e | Right a

This dichotomy between the Ok (or Right) value and the Error value (or the Left one) makes it a great vehicle for carrying results of functions that can fail.

In Rust, this replaces the traditional error handling mechanisms based on exceptions. In Haskell, the exceptions are present and sometimes necessary, but Either is nevertheless the preferred approach to dealing with errors.

What to do?

One thing that Haskell does better is composing those fallible functions into bigger chunks of logic.

Relatively recently, Rust has added the ? operator as a replacement for the try! macro. This is now the preferred way of error propagation, allowing for a more concise composition of functions that return Results:

/// Read an integer from given file.
fn int_from_file(path: &Path) -> io::Result<i32> {
    let mut file = fs::File::open(path)?;
    let mut s = String::new();
    file.read_to_string(&mut s)?;
    let result = s.parse().map_err(|e| io::Error::new(io::ErrorKind::InvalidData, e))?;
    Ok(result)
}

But Haskell had it for much longer, and it’s something of a hallmark of the language and functional programming in general — even though it looks thoroughly imperative:

intFromFile :: FilePath -> IO Int
intFromFile path = do
    s <- readFile path
    i <- readIO s
    return i

If you haven’t seen it before, this is of course a monad — the IO monad, to be precise. While discussing monads in detail is way outside of the scope of this article, we can definitely notice some analogies with Rust. The do notation with <- arrows is evidently similar to how in Rust you’d assign the result of a fallible operation after “unpacking” it with ?.

But of course, there’s plenty of different monads in Haskell: not just IO, but also Either, Maybe, Reader, Writer, Cont, STM, and many others. In Rust (at least as of 1.19), the ? operator only works for Result types, although there is some talk about extending it to Option as well6.

Eventually, we may see the language adopt some variant of the do notation, though the motivation for this will most likely come from asynchronous programming with Futures rather than plain Results. General monads, however, require support for higher kinded types which isn’t coming anytime soon.

A path through Rust?

Now that we’ve discussed those similarities, the obvious question arises.

Is learning Rust worthwhile if your ultimate goal is getting proficient at functional programming in general, or Haskell in particular?

My answer to that is actually pretty straightforward.

If “getting to FP” is your main goal, then Rust will not help you very much. Functional paradigm isn’t the main idea behind the language — its shtick is mostly memory safety, and zero-cost abstractions. While it succeeds somewhat at being “Haskell Lite”, it really strives to be safer C++7.

But if, on the other hand, you regard FP mostly as a curiosity that seems to be seeping into your favorite imperative language at an increasing rate, Rust can be a good way to gain familiarity with this peculiar beast.

At the very least, you will learn the functional way of modeling programs, with lots of smart enums/unions and structs but without inheritance.

And the best part is: you will be so busy fighting the borrow checker you won’t even notice when it happens ;-)


  1. Just ask in #haskell-beginners on Freenode if you’re interested. 

  2. Though ironically, I found the CT lectures by Bartosz Milewski very helpful in developing the right intuitions, even though they’re very abstract. 

  3. For example, Haskell has green threads (created with forkIO) which are somewhat similar to goroutines from Go. To get anything remotely similar in Rust, you need to use external libraries

  4. Note that such containers aren’t very idiomatic Haskell. A more typical solution would be to just curry the draw function, implicitly putting the Draw object inside its closure. 

  5. This mechanisms expands to associated constants in Rust 1.20. 

  6. Those two types also have a form of monadic bind (>>= in Haskell) exposed as the and_then method

  7. If you want another language for easing into the concept of functional programming, I’ve heard that Scala fills that niche quite well. 

Continue reading

Long Live Dynamic Languages!

Posted on Wed 24 May 2017 in Programming • Tagged with Python, Rust, dynamic languages, dynamic typing, static typingLeave a comment

If you followed the few (or a dozen) of my recent posts, you’ve probably noticed a sizable bias in the choice of topics. The vast majority were about Rust — a native, bare metal, statically typed language with powerful compile time semantics but little in the way of runtime flexibility.

Needless to say, Rust is radically different than (almost the exact opposite of) Python, the other language that I’m covering sometimes. Considering this topical shift, it would fair to assume that I, too, have subscribed to the whole Static Typing™ trend.

But that wouldn’t be very accurate.

Don’t get me wrong. As far as fashion cycles in the software industry go, the current trend towards static/compiled languages is difficult to disparage. Strong in both hype and merit, it has given us some really innovative & promising solutions (as well as some not-so-innovative ones) that are poised to shape the future of programming for years, if not decades to come. In many ways, it is also correcting mistakes of the previous generation: excessive boilerplate, byzantine abstractions, and software bloat.

What about dynamic languages, then? Are they slowly going the way of the dodo?

Trigger warning: TypeError

Some programmers would certainly wish so.

Indeed, it’s not hard at all to find articles and opinions about dynamic languages that are, well, less than flattering.

The common argument echoed in those accounts points to supposed unsuitability of Python et al. for any large, multi-person project. The reasoning can be summed up as “good for small scripts and not much else”. Without statically checked types, the argument goes, anything bigger than a quick hack or a prototype shall inevitably become hairy and dangerous monstrosity.

And when that happens, a single typo can go unchecked and bring down the entire system!…

At the very end of this spectrum of beliefs, some pundits may eventually make the leap from languages to people. If dynamically typed languages (or “untyped” ones, as they’re often mislabeled) are letting even trivial bugs through, then obviously anyone who wants to use them is dangerously irresponsible. It must follow that all they really want is to hack up some shoddy code, yolo it over to production, and let others worry about the consequences.

Mind the gap

It’s likely unproductive to engage with someone who’s that extreme. If the rhetoric is dialed down, however, we can definitely find the edge of reason.

In my opinion, this fine line goes right through the “good in small quantities” argument. I can certainly understand the apprehension towards large projects that utilize dynamically typed languages throughout their codebases. The prospect of such a project is scary, because it contains an additional element of uncertainty. More so than with many other technologies, you ought to know what you’re doing.

Some people (and teams) do. Others, not so much.

I would therefore refine the argument so that it better reflects the strengths and weaknesses of dynamic languages. They are perfectly suited for at least the following cases:

  • anyone writing small, standalone applications or scripts
  • any project (large or small) with a well-functioning team of talented individuals

The sad reality of the software industry is the vast, gaping chasm of calamity and despair that stretches between those two scenarios.

Within lies the bulk of commercial software projects, consistently hamstrung by the usual suspects: incompetent management, unclear and shifting requirements, under- or overstaffing, ancient development practices, lack of coding standards, rampant bureaucracy, inexperienced developers, and so on.

In such an environment, it becomes nigh impossible to capitalize on the strengths of dynamic languages. Instead, the main priority is to protect from even further productivity losses, which is what bog-standard languages like Java, C#, or Go tend to be pretty good at. Rather than to move fast, the objective is to remain moving at all.

Freedom of choice

But that’s backwards”, the usual retort goes. “Static typing and compilation checks are what enables me to be productive!”

I have no doubt that most people saying this do indeed believe they’re better off programming in static languages. Regardless of what they think, however, there exists no conclusive evidence to back up such claims as a universal rule.

This is of course the perennial problem with software engineering in general, and the project management aspect of it in particular. There is very little proper research on optimal and effective approaches to it, which is why any of the so-called “best practices” are quite likely to stem from unsubstantiated hearsay.

We can lament this state of affairs, of course. But on the other hand, we can also find it liberating. In the absence of rigid prescriptions and judgments about productivity, we are free to explore, within technical limitations, what language works best for us, our team, and our projects.

Sometimes it’ll be Go, Java, Rust, or even Haskell.
A different situation may be best handled by Python, Ruby, or even JavaScript.

As the old adage goes, there is no silver bullet. We should not try to polish static typing into one.

Continue reading

Asynchronous Rust for fun & profit

Posted on Fri 28 April 2017 in Programming • Tagged with Rust, async, Tokio, futures, HTTPLeave a comment

…or: Is Rust webscale?

In this day and age, no language can really make an impact anymore unless it enables its programmers to harness the power of the Internet. Rust is no different here. Despite posing as a true systems language (as opposed to those only marketed as such), it includes highly scalable servers as a prominent objective in its 2017 agenda.

Presumably to satisfy this very objective, the Rust ecosystem has recently seen some major developments in the space of asynchronous I/O. Given the pace of those improvements, it may seem that production quality async services are quite possible already.

But is that so? How exactly do you write async Rust servers in the early to mid 2017?

To find out, I set to code up a toy application. Said program was a small intermediary/API server (a “microservice”, if you will) that tries to hit many of the typical requirements that arise in such projects. The main objective was to test the limits of asynchronous Rust, and see how easily (or difficult) they can be pushed.

This post is a summary of all the lessons I’ve learned from that.

It is necessarily quite long, so if you look for some TL;DR, scroll down straight to Conclusions.

Asynchro-what?

Before we dive in, I have to clarify what “asynchronous” means in this context. Those familiar with async concepts can freely skip this section.

Pulling some threads

Asynchronous processing (or async for short) is brought up most often in the context of I/O operations: disk reads, network calls, database queries, and so on.

Relatively speaking, all those tasks tend to be slow: they take orders of magnitude longer than just executing code or even accessing RAM. The “traditional” (synchronous) approach to dealing with them is to relegate those tasks to separate threads.

When one thread has to wait for a lengthy I/O operation to complete, the operating system (its scheduler, to be precise) can suspend that thread. This lets others execute their code in the mean time and not waste CPU cycles.

This is the essence of concurrency1.

Schedule yourself

But threads are not the only option when dealing with many things (i.e. requests) at once.

The alternative approach is one where no threads are automatically suspended or resumed by the OS. Instead, a special version of I/O subroutines allows the program to continue execution immediately after issuing an I/O call. While the operation happens in the background2, the code is given an opaque handle — usually called a promise, a future, or an async result — that will eventually resolve to the actual return value.

The program can wait for the handle synchronously, but it would typically hand it over to an event loop, an abstraction provided by a dedicated async framework. Such a framework (among which node.js is probably the best known example) maintains a list of all I/O “descriptors” (fds in Unix) that are associated with pending I/O operations.

Then, in the loop, it simply waits on all of them, usually via the epoll system call. Whenever an I/O task completes, the loop would execute a callback associated with its result (or promise, or future). Through this callback, the application is able to process it.

In a sense, we can treat the event loop as a dedicated scheduler for its program.

But why?

So, what exactly the benefit of asynchronous I/O? If anything, it definitely sounds more complicated for the programmer. (Spoiler alert: it is).

The impetus for the development of async techniques most likely came from the C10K problem. The short version of it is that computers are nowadays very fast and should therefore be able to serve thousands of requests simultaneously. (especially when those requests are mostly I/O, which translate to waiting time for the CPU).

And if “serving” queries is indeed almost all waiting, then handling thousands of clients should be very possible.

In some cases, however, it was found that when the OS is scheduling the threads, it introduces too much overhead on the frequent pause/resume state changes (context switching). Like I mentioned above, the asynchronous alternative does away with all that, and indeed lets the CPU just wait (on epoll) until something interesting happens. Once it does, the application can deal with it quickly, issue another I/O call, and let the server go back to waiting.

With today’s processing power we can theoretically handle a lot of concurrent clients this way: up to hundreds of thousands or even millions.

Reality check

Well, ain’t that grand? No wonder everyone is writing everything in node.js now!

Jokes aside, the actual benefits of asynchronous I/O (especially when weighed against its inconvenience for developers) are a bit harder to quantify. For one, they rely heavily on the assumption of fast code & slow I/O being valid in all situations.

But this isn’t really self-evident, and becomes increasingly dubious as time goes on and code complexity grows. It should be obvious, for example, that a Python web frontend talking mostly to in-memory caches in the same datacenter will have radically different performance characteristics than a C++ proxy server calling HTTP APIs over public Internet. Those nuances are often lost in translation between simplistic benchmarks and exaggerated blog posts3.

Upon a closer look, however, these details point quite clearly in favor of asynchronous Rust. Being a language that compiles to native code, it should usually run faster than interpreted (Python, Ruby) or even JITed (JVM & .NET) languages, very close to what is typically referred to as “bare metal” speed. For async I/O, it means the event loop won’t be disturbed for a (relatively) long time to do some trivial processing, leading to higher potential throughput of requests.

All in all, it would seem that Rust is one of the few languages where async actually makes sense.

Rust: the story so far

Obviously, this means it’s been built into the language right from the start… right?

Well, not really. It was always possible to use native epoll through FFI, of course, but that’s not exactly the level of abstraction we’d like to work with. Still, the upper layers of the async I/O stack have been steadily growing at least since Rust 1.0.

The major milestones here include mio, a comparatively basic building block that provides an asynchronous version of TCP/IP. It also offers idiomatic wrappers over epoll, allowing us to write our own event loop.

On the application side, the futures crate abstracts the notion of a potentially incomplete operation into, well, a future. Manipulating those futures is how one can now write asynchronous code in Rust.

More recently, Tokio has been emerging as defacto framework for async I/O in Rust. It essentially combines the two previously mentioned crates, and provides additional abstractions specifically for network clients and servers.

And finally, the popular HTTP framework Hyper is now also supporting asynchronous request handling via Tokio. What this means is that bread-and-butter of the Internet’s application layer — API servers talking JSON over HTTP — should now be fully supported by the ecosystem of asynchronous Rust.

Let’s take it for a spin then, shall we?

The Grand Project

Earlier on, we have established that the main use case for asynchronous I/O is intermediate microservices. They often sit somewhere between a standard web frontend and a storage server or a database. Because of their typical role within a bigger system, these kinds of projects don’t tend to be particularly exciting on their own.

But perhaps we can liven them up a little.

In the end, it is all about the Internet that we’re talking here, and everything on the Internet can usually be improved by one simple addition.


Image source

…Okay, two possible additions — the other one being:

Memes!

If you’re really pedantic, you may call them image macros. But regardless of the name, the important part is putting text on pictures, preferably in a funny way.

The microservice I wrote is doing just that. Thought it won’t ensure your memes are sufficiently hilarious, it will try to deliver them exactly to your specifications. You may thus think of it as possible backend for an image site like this one.

Flimsy excuses & post-hoc justifications

It is, of course, a complete coincidence, lacking any premeditation on my part, that when it comes to evaluating an async platform, a service like this fits the bill very well.

And especially when said platform is async Rust.

Why, though, is it such a happy, er, accident?

  • It’s a simple, well-defined application. There is basically a single endpoint, accepting simple input (JSON or query string) and producing a straightforward result (an image). No need to persist any state made creating an MVP significantly easier.

  • Caching can be used for meme templates and fonts. Besides being an inherent part of most network services, a cache also represents a point of contention for Rust programs. The language is widely known for its alergy to global mutable state, which is exactly what programmatic caches boil down to.

  • Image captioning is a CPU-intensive operation. While the “async” part of async I/O may sometimes go all the way down, many practical services either evolve some important CPU-bound code, or require it right from the start. For this reason, I wanted to check if & how async Rust can mix with threaded concurrency.

  • Configuration knobs can be added. Unlike trivial experiments in the vein of an echo or “Hello world” server, this kind of service warrants some flags that the user could tweak, like the number of image captioning threads, or the size of the template cache. We can see how easy (or how hard) it is to make them applicable across all future-based requests.

All in all, and despite its frivolous subject matter, a meme server is actually hitting quite a few notable spots in the microservice domain.

Learnings

As you may glean from its GitHub repo, it would seem that the experiment was successful. Sure, you could implement some features in the captioning department (supporting animated GIFs comes to mind), but none of these are pertinent to the async mechanics of the server.

And since it’s the async (I/O) in Rust that we’re interested in, let me now present you with an assorted collection of practical experiences with it.

>0-cost futures

If you read the docs’ preamble to the futures crate, you will see it mentioning the “zero-cost” aspect of the library. Consistent with the philosophy behind Rust, it proclaims to deliver its abstractions without any overhead.

Thing is, I’m not sure how this promise can be delivered on in practice.

Flip through the introductory tutorial to Tokio, for example, and you will already find plenty of compromises. Without the crucial (but nightly-only) impl Trait feature, you are basically required to put all your futures in a Box4. They even encourage it themselves, offering a convenient Future::boxed method exactly for this purpose, as well the matching BoxFuture typedef right in the crate.

But hey, you can always just use nightly Rust, right? impl Trait will stabilize eventually, so your code should be, ahem, future-proof either way.

Unfortunately, this assumes all the futures that you’re building your request handlers from shall never cross any thread boundaries. (BoxFuture, for example, automatically constrains them to be Send). As you’ve likely guessed, this doesn’t jive very well with computationally intensive tasks which are best relegated to a separate thread.

To deal with them properly, you’re going to need a thread pool-based executor, which is currently implemented in the futures_cpupool crate. Using it requires a lot of care, though, and a deep understanding of both types of concurrency involved.

Evidently, this was something that I lacked at the time, which is why I encountered problems ensuring that my futures are properly Send. In the end, I settled on making them Send in the most straightforward (and completely unnecessary) manner: by wrapping them in Arc/Mutex. That in itself wasn’t without its perils, but at least allowed me to move forward.

Ironically, this also shows an important, pragmatic property of the futures’ system: sub-par hacks around it are possible — a fact you’ll be glad to know about on the proverbial day before a deadline.

Templates-worthy error messages

Other significant properties of the futures’ abstraction shall include telling the programmer what’s wrong with his code in the simplest, most straightforward, and concise manner possible.

Here, let me show you an example:


…which you can also behold in its gist form .

The reason you will encounter such incomprehensible messages stems from the very building blocks of async code.

Right now, each chained operation on a future — map, and_then, or_else, and so on — produces a nested type. Every subsequent application of those methods “contains” (in terms of the type system) all the previous ones. Keep going, and it will eventually balloon into one big onion of Chain<Map<OrElse<Chain<Map<...etc...>>>>>.


Futures are like ogres.

I haven’t personally hit any compiler limits in this regard, but I’m sure it is plausible for a complicated, real-world program.

It also gets worse if you use nightly Rust with impl Trait. In this case, function boundaries no longer “break” type stacking via Boxing the results into trait objects. Indeed, you can very well end up with some truly gigantic constructs as the compiler tries represent the return types of your most complex handlers.

But even if rustc is up to snuff and can deal with those fractals just fine, it doesn’t necessarily mean the programmer can. Looking at those error messages, I had vivid flashbacks from hacking on C++ templates with ancient compilers like VS2005. The difference is, of course, that we’re not trying any arcane metaprogramming here; we just want to do some relatively mundane I/O.

I have no doubt the messaging will eventually improve, and the mile-long types will at least get pretty-printed. At the moment, however, prepare for some serious squinting and bracket-counting.

Where is my (language) support?

Sadly, those long, cryptic error messages are not the only way in which the Rust compiler disappoints us.

I keep mentioning impl Trait as a generally desirable language feature for writers of asynchronous code. This improvement is still a relatively long way from getting precisely defined, much less stabilized. And it is only a somewhat minor improvement in the async ergonomics.

The wishlist is vastly longer and even more inchoate.

Saying it bluntly, right now Rust doesn’t really support the async style at all. All the combined API surface of futures/Tokio/Hyper/etc. is a clever, but ultimately contrived design, and it has no intentional backing in the Rust language itself.

This is a stark contrast with numerous other languages. They often support asynchronous I/O as something of a first class feature. The list includes at least C#, Python 3.5+, Hack/PHP, ES8 / JavaScript, and basically all the functional languages. They all have dedicated async, await, or equivalent constructs that make the callback-based nature of asynchronous code essentially transparent.

The absence of similar support puts Rust in the same bucket as frontend JavaScript circa 2010, where .then-chaining of promises reigned supreme. This is of course better than the callback hell of early Node, but I wouldn’t think that’s a particularly high bar. In this regard, Rust leaves plenty to be desired.

There are proposals, obviously, to bring async coroutines into Rust. There is an even broader wish to make the language cross the OOP/FP fence already and commit to the functional way; this would mean adding an equivalent of Haskell’s do notation.

Either development could be sufficient. Both, however, require significant amount of design and implementation work. If solved now, this would easily be the most significant addition to the language since its 1.0 release — but the solution is currently in the RFC stages at best.

Future<Ecosystem>

While the core language support is lacking, the great as usual Rust community has been picking up some of the slack by establishing and cultivating a steadily growing ecosystem.

The constellation of async-related crates clusters mostly around the two core libraries: futures crate itself and Tokio. Any functionality you may need while writing asynchronous should likely be found quite easily by searching for one of those two keywords (plus Rust, of course). Another way of finding what you need is to look at the list of Tokio-related crates directly.

To be fair, I can’t really say much about the completeness of this ecosystem. The project didn’t really require too many external dependencies — the only relevant ones were:

  • futures_cpupool mentioned before
  • tokio-timer for imposing a timeout on caption requests
  • tokio-signal which handles SIGINT/Ctrl+C and allows for a graceful shutdown

Normally, you’d also want to research the async database drivers for your storage system of choice. I would not expect anything resembling the Diesel ORM crate, though, nor a web framework comparable to Iron, Pencil, or Rocket.

Conclusions

Alright, so what can we get from this overall analysis?

Given the rapid development of async Rust ecosystem so far, it is clear the technology is very promising. If the community maintains its usual enthusiasm and keeps funneling it into Tokio et al., it won’t be long before it matures into something remarkable.

Right now, however, it exposes way too many rough edges to fully bet on it. Still, there may be some applications where you could get away with an async Rust backend even in production. But personally, I wouldn’t recommend it outside of non-essential services, or tools internal to your organization.

If you do use async Rust for microservices, I’d also advise to take steps to ensure they remain “micro”. Like I’ve elaborated in the earlier sections, there are several issues that make future-based Rust code scale poorly with respect to maintainability. Keeping it simple is therefore essential.

To sum up, async Rust is currently an option only for the adventurous and/or small. Others should stick to a tried & tested solution: something like Java (with Quasar), .NET, Go, or perhaps node.js at the very least.


  1. It is also the crux of parallelism, but that’s different and is not the focus here. 

  2. Background” here refers to the low level, innate concurrency of the OS kernel (mediated with hardware interrupts), not the epoll-based event loops on the application side. 

  3. There is a great parallel to be drawn between a trivial echo/Hello world server, and a 3D graphics program that only redraws an empty screen. Both may start at some very high performance numbers (requests/frames per second) but once you start adding practical stuff, those metrics must drop hyperbolically

  4. Technically, you are not, but the alternative is extremely cumbersome.
    In short, you’d have to follow an approach similar to custom Iterators: define a new struct for each individual case (possibly just newtype‘ing an existing one), and then implement the necessary trait for it.
    For iterators, this works reasonably well, and you don’t need custom ones that often anyway. But futures, by their very nature, are meant to encapsulate any computation. For them, “each individual case” is literally every asynchronous function in your code. 

Continue reading

A tale of two Rusts

Posted on Sat 24 December 2016 in Programming • Tagged with Rust, nightly Rust, stable Rust, Rocket.rsLeave a comment

The writing has been on the wall for many months now, but I think the time has come when we can officially declare it.

Stable Rust is dead. Nightly Rust is the only Rust.

Say what?

If you’re out of the loop, Rust is this newfangled system programming language. Rust is meant to fit in the niches normally occupied by C, so its domain includes performance-sensitive and safety-critical applications. Embedded programming, OS kernels, databases, servers, and similar low-level pieces of computing and networking infrastructure are all within its purview.

Of course, this “replacing C” thing is still an ambition that’s years or decades away. But in theory, there is nothing preventing it from happening. The main thing Rust would need here is time: time to buy trust of developers by having been used in real-world, production scenarios without issues.

To facilitate this (and for other reasons), Rust has been using three release channels with varying frequency of updates. There are the stable, beta, and nightly Rust. Of those, beta is pretty much an RC for a future stable release, so there aren’t many differences at all between the first two channels.

Nightly perks

This cannot be said about nightly.

In fact, nightly Rust is essentially its own language.

First, there is a number of exclusive language features that are only available on nightly. They are all guarded by numerous #![feature(...)] gates which are required to activate them. Because stable Rust doesn’t accept any such directive, trying to compile code that uses them will fail on a non-nightly compiler.

This has been justified as a necessary step for testing out new features in real scenarios, or at least those that resemble (stable) reality as close as possible. Indeed, many features did eventually land in stable Rust by going through this route — a recent example would be the ? operator, an error-handling measure analogous to the try! macro.

But some features take a lot of time to stabilize. And few (like zero_one which guards the numeric traits Zero and One) may even be deprecated without ever getting out of the nightly channel.

Unplugged

Secondly, and most importantly, there is at least one feature that won’t get stabilized ever:

#![feature(plugin)]

And it’s all by design.

This plugin switch is what’s necessary to include #![plugin(...)] directives. Those in turn activate compiler plugins: user-provided additions to the compiler itself. Plugins operate against the API provided directly by rustc and enhance its capabilities beyond what the language normally provides.

Although it sounds rather ominous, the vast majority of plugins in the wild serve a singular purpose: code generation. They are written with the sole purpose of combating Rust’s rigidity, including the (perfectly expected) lack of dynamic runtime capabilities and the (disappointingly) stiff limits of its wanting macro system.

This is how they are utilized by Diesel, for example, a popular ORM and SQL query interface; or Serde, a serialization framework.

Why compiler plugins can never be stable, though? It’s because the internal API they are coded against goes too deep into the compiler bowels to ever get stabilized. If it were, it would severely limit the ability to further develop the language without significant breakage of the established plugins.

Pseudo-stable

Wait,” you may ask, “how do we even talk about «established» compiler plugins? Shouldn’t they be, by their very definition, unstable?”

Well… yes. They definitely should. And therein lies the crux of the problem.

Turns out, plugins & nightly Rust are only mostly treated as unstable.

In reality, the comfort and convenience provided by nightly versions of many libraries — all of which rely on compiler plugins — is difficult to overstate. While their stable approximations are available, they at best require rather complicated setup.

What’s always involved is a custom build step, and usually a separate file for the relevant code symbols and declarations. In the end, we get a bunch of autogenerated modules whose prior non-existence during development may also confuse IDEs and autocompletion tools.

For all those reasons and more, an ecosystem has developed where several popular libraries are “nightly but pseudo-stable”. This includes some key components in many serious applications, like the aforementioned ORM & serialization crates.

The precedent

And so has been the state of affairs until very recently. The nightly Rust has been offering some extremely enticing features, but the stable channel was at least paid a lip service to. However, the mentality among library authors that “nightly-first” is an acceptable policy had been strong for a long time now.

No wonder it has finally shifted towards “nightly-only”.

Meet Rocket, the latest contestant in the already rich lineup of Rust web frameworks. Everything about it is really slick: a flashy designer website; approachable and comprehensive documentation; and concise, Flask-like API for routing and response handling. Predictably, it’s been making quite a buzz on Reddit and elsewhere.

There is just an itty bitty little problem: Rocket only works on nightly. No alternatives, no codegen shims… and no prospects of any change in the foreseeable future. Yet, there doesn’t seem to be many people concerned about this, so clearly this is (a new?) norm.

The Rusts split

In essence, Rust is now two separate languages.

The stable-nightly divide has essentially evolved into something that closely resembles the early stages of the 2.x vs. 3.x split in the Python world. The people still “stuck” on 2.7 (i.e. stable) were “holdouts”, and the future was with 3.x (nightly). Sure, there have been some pithy backports (feature stabilizations), but the interesting stuff has been happening on the other side.

It’s astonishing that Rust managed to replicate this phenomenon without any major version bumps, and with no backwards-incompatible releases. Technically, everything is still version 1.x.. Not even Cargo, the Rust package manager, recognizes the stable-nightly distinction.

But that’s hardly any consolation when you try to install a nightly-only crate on stable Rust. You will download it just fine, and get all the way to compiling its code, only to have it error out due to unsupported #![feature(...)] declarations.

What now?

The natural question is, can this situation be effectively addressed?

I hope it’s obvious why stable Rust cannot suddenly start supporting compiler plugins. Given that they rely on rustc internals which aren’t standardized, doing so would be contrary to the very definition of a “stable” release channel.

The other option is to fully embrace nightly as de facto recommended toolchain. This has been informally happening already, despite the contrary recommendations in the official docs.

The downsides are obvious here, though: nightly Rust is not a misnomer at all. The compiler is in active development and its build breaks often. Some of those breakages make it into nightly releases with unsatisfying regularity.

Of course, there was also another option: stick to the intended purpose of release channels and don’t build castles on the sand by publishing nightly-first or nightly-only crates. This ship seems to have sailed by now, as the community has collectively decided otherwise.

Oh well.

It’s just a little ironic that in a language that is so focused on safety, everyone is perfectly happy with an unstable compiler.

Continue reading

Please don’t use Click

Posted on Fri 20 May 2016 in Programming • Tagged with Python, CLI, UI, ClickLeave a comment

…not for standalone programs anyway.

Chances are, you have written some command line programs in Python. This is quite probable even if you normally code in some other language. And if you have, it is not unlikely that you needed to parse the argv of your program at one point or another.

There are plenty of options here, both in the standard library as well as among third party packages. One does stand out, however, and it’s mostly for how it is often overused. I’m talking about Click here.

If you wanted to use it in your next Python program, I hereby urge you to reconsider.

What’s the fuss?

click_ The somewhat bizarrely named Click library is described as a “package for creating beautiful command line interfaces”. Its main trick is the ability to create subcommands by adorning Python functions with the @click.command() decorator1. It then makes them coalesce into an argument parser, equipped with the necessary dispatching logic.

This idea isn’t new, of course. Prior art goes back at least seven years to the now-abandoned opster package. Click, however, was the first one of its kind to garner noticeable popularity, which is easily attributed to whom it’s been authored by.

So while my arguments against using this kind of CLI framework would apply to any package implementing the paradigm, it just happens that Click is currently its most prominent example. Purely for the sake of convenience, I will therefore refer to it as if it was interchangeable with the whole concept. Because why not? Whatever you may say about the library’s name, it’s hard to imagine a more concise moniker than a simple Click.

What’s wrong, then, with the way Click handles command line interfaces?

CLI: Little Interfaces

It’s how it encourages to treat them as an accidental afterthought rather than a deliberate design decision.

For applications invoked repeatedly from a terminal, their command line arguments and flags are the primary means of user interaction2. It is how users communicate their intent to perform an action; provide the neccessary input data to carry it throgh; decide how they want to receive the output; and control many other aspects of the programs execution. Absent graphical components and widgets, the command line is virtually the only way to interact with a terminal program.

In other words, it is the UI.

And how important the UI is for any application? It seems to be important enough that entire fields of study are devoted to reducing friction of human-computer interaction. In many projects, the emphasis on user interface design is on par with that of actual software engineering.
Like everything, of course, it is susceptible to trends and fads (such as the recent “mobile/responsive everything!” craze). But its significance remains undiminished. Quite the opposite: in the age of ubiquitous computing, user interfaces are probably more important than ever.

Yes, this includes CLI. One of the main reasons we turn to the command line are speed and efficacy. Common tasks must utilize short and convenient syntax that is quick to integrate into user’s muscle memory. Others should not only be possible, but discoverable and accessible without going through reams of man pages.

Any terminal program intended for frequent use by humans should therefore strive to excel in those two qualities. But except for the simplest of cases, it won’t happen by itself. Designing an efficient CLI for any non-trivial application is a challenging and demanding task.

It doesn’t click

With Click, however, we’re encouraged to just wing it.

Click tells us to slap some decorators on our top-level functions and call it a day. Sure, you can dig deep enough and uncover the underlying layers of abstraction that may eventually allow you do things for which argparse has a first-class support.

By default, however, Click shoehorns your programs into predefined patterns that, incidentally, mirror those of some least intuitive command-line tools in existence.

Indeed, the whole idea of subdiving your program into several distinct is already suspect, for it appears at odds with the fundamental Unix philosophy of doing one thing well. While it is occasionally justified, it shouldn’t be the first thing that comes to your mind. But that’s completely at odds with the Click’s approach, where not ending up with multiple distinct commands is something you have to consciously avoid.

…though it sometimes might

So, what am I suggesting you use instead libraries such as Click?… Nothing outrageous, really.

If you care about your command line interface, consider just using the argparse module. Yes, it will force you to create parser objects, add arguments & flags to it, and in general pay some attention to the whole business. When it comes to UI, it’s always good to make it an explicit concern, maybe even sufficient to warrant its own module.

Alternatively, the docopt library provides another take on the UI-first approach to CLI, though it is more limited in its capabilities3.

Finally, I’m not advocating to ditch Click in all scenarios. There’s plenty of situations when we’re interested in getting any CLI up and running, and not so much in making the most efficient and intuitive interface possible. The prime example is any kind of automation scripts that are ancillary to some bigger project, like manage.py is in Django4. The Python ecosystem doesn’t really have dedicated task runners that are as featureful as Grunt or Gulp, and that makes Click a viable and compelling option5.

But for standalone programs whose CLI is the main interface? Yeah, not really.


  1. Oddly enough, that pair of parentheses seems to be mandatory. 

  2. Environment variables and config files deserve a honorary mention, of course. But those are usually derivatives of the command line arguments, containing e.g. the default values for flags. 

  3. Click’s own documentation actually describes quite nicely how theirs and docopt’s philosophies differ in a way that’s consistent with this article. 

  4. Incidentally, this appears to be a major motivation behind creating Click in the first place: to support web applications built upon on the Flask framework, and possibly obviate the need for extensions such as Flask-Script

  5. This saying, there are some task runners which offer similar experience, like Invoke

Continue reading

Package managers’ appreciation day

Posted on Sat 26 March 2016 in Programming • Tagged with packages, package manager, node.js, npm, C++Leave a comment

By now you have probably heard about the infamous “npm-gate” that swept through the developer community over the last week. It has been brought up, discussed, covered, meta-discussed, satirized, and even featured by some mainstream media. Evidently the nerds have managed to stir up some serious trouble again, and it only took them 11 lines of that strange thing they call “code”.

No good things in small packages

When looking for a culprit, the one party that everyone pounced on immediately was of course the npm itself. With its myriad of packages that could each fit in a tweet, it invites to create the exact house of cards we’ve seen collapse.

This serves as a good wake-up call, of course. But it also compels to throw the baby out with the bathwater, and draw a conclusion that may be a little too far-fetched. Like perhaps declaring the entire idea of managing dependencies “the npm way” suspect. If packages tend to degenerate into something as ludicrous as isArray — to say nothing of left-pad, which started the whole debacle — then maybe this approach to software reusability has simply bankrupted itself?

A world without *pm

I’m right away responding to that with a resounding “No!”. Package management as a concept is not responsible for the poor decision making of one specific developer collective. And anyone who might think tools like npm do more harm than good I ask: have you recently written any C++?

See, C++ is the odd one among languages that at least pretend to be keeping up with the times. It doesn’t present a package management story at all. That’s right — the C++ “ecosystem”, as it stands now, has:

  • no package manager
  • no repository of packages
  • no unified way of managing dependencies
  • no way to isolate development environments of different projects from one another

Adding any kind of third-party dependency to a C++ project — especially a portable one, which is allegedly one of C++’s strengths — is a considerable pain, even when it doesn’t require any additional libraries by itself. And environment isolation? Some people are using Linux containers (!) for this, which is like dealing with a mosquito by shooting it with a howitzer.

Billions upon billions of lines
To build a C++ binary, you must first build the userspace.

But hey, at least they can use apt-get, right?…

So, string padding incidents aside, package managers are absolutely essential. Sure, we can and should discuss the merits of their particular flavors and implementation details —like whether it’s prudent to allow “delisting” of packages. As a whole, however, package managers deserve recognition as a crucial part of modern language tooling that we cannot really do without.

Continue reading

You Don’t Have to Interview like Google

Posted on Mon 28 December 2015 in Programming • Tagged with Google, interviews, startups, career, hiringLeave a comment

If you look at discussion forums for people in the CS industry — like /r/cscareequestions or even just Hacker News — you’ll find lots of talk about the so called Big Four companies.

This is mostly in the context of applying to them, or going through their interview process. Which of the large software corporations are discussed here tends to fluctuate a little bit, but both Google and Microsoft are invariably included, with Facebook popping up more often than not.

Because of their privileged positions as very desirable places to work, these companies tend to be taken as models for others to mimic1. Probably the most apparent and direct outcome is the increasing prevalence of “Google-style” interviews, which are now utilized by countless software shops around the world.

Whiteboard coding is how they are often called. It is a subject of an intense debate, whether or not they “work”, and adequately assess the engineering aptitude of candidates. If some high profile anecdotes are of any indication, the most common complaint is that they fail to recognize competence by ignoring previous professional work, open source contributions, conference talks, and so on.

Instead, the whiteboard interview requires demand showing a “pure” problem solving ability within a relatively short time window, all without some broader context or even the usual tools of the trade: laptop, editor, and a search engine.

As a Googler who had gone through this process and has now conducted a few of those interviews himself, I find those complaints mostly valid albeit misdirected.

The problem isn’t really that Google interviews like it does.

What’s really the issue is other companies implementing the same process, and not realizing it cannot possibly work for them.

Somewhat special

It is important to understand that Google’s stance on interviewing is influenced by some unique circumstances:

  • very high and steady influx of potential candidates

  • comparatively long tenure of the average engineer and the general focus on employee retention

  • huge and mostly proprietary software stack working at a scale that almost no others do

From this perspective, it makes sense to utilize cautious hiring strategies that may result in a high ratio of false negatives2. When rejections are cheap but the new hires are supposed to be here for the long run — partially because of the long ramp-up time necessary to become productive — it can be costly to give candidates the benefit of the doubt.

The last point also explains why proficiency with specific technologies is less useful than general flexibility grounded in strong fundamentals. To put it shortly, Google prefers you know CS rather than CSS.

Finally, whiteboard coding is just one input to the evaluation process, but it tends to be the most trustworthy one. Besides programming aptitude, the ideal candidate would show a proven track record of technical leadership while tackling complex problems that span a broad scope.
Unfortunately, those qualities are difficult to convey efficiently and reliably through the usual industry channels: a resume, references from previous jobs, GitHub profile, etc.

Different conditions

Given the above reasoning as to why “Google-style” interviews seem to work well for Google, I hope it’s evident why they are likely a poor choice for companies that don’t share the same characteristics as the Big 4.

For one, it is highly unusual for a software shop in today’s market to command a sizeable pool for qualified candidates. Software engineering vacancies often go unfilled for weeks and months, even if the company isn’t exactly looking for “rockstars”, “ninjas”, “gunslingers”, or whatever the silly term du jour is. Those who meet the requirements usually have their pick at many different offers, too.

The reality for many companies (especially startups) is also one where they are unable or unwilling to invest much in the retention of their employees. Because the employment relationship in this industry tends to be quite volatile (which isn’t necessarily a bad thing), it often makes sense for companies to look for a near-immediate payoff when hiring.

We owe it to the prevalent open source technologies that this isn’t entirely unreasonable. If your software stack is composed entirely of components that are available in the open, you can probably find engineers who are familiar with most of them. They can be productive members of your team almost literally from day one!

Right tool for the job

The most important observation is that every company is different, and following the One True Best Practice™ will likely prevent you from utilizing the best qualities of your work place. Smaller shops, for example, could take a more personalized approach to hiring: let candidates actually sit with engineers, solve real-life problems, and have deep technical conversations.

Of course, you may still find whiteboard coding valuable in its own right. Indeed, a simple test for at least the basic programming skill appears to be a necessary sanity check.

But a full suite of difficult technical interviews with tough algorithmic problems that last a better part of the day? Most likely not.


  1. Some seem to have succeeded to such an extent that you may occasionally hear about “Big N”. This often includes some currently large and/or successful but still “hip” startups. IT is such a fashion industry sometimes… 

  2. Though on the flip side, it exacerbates the impostor syndrome among people who do get hired, as their success could easily be construed as mostly luck. 

Continue reading

Don’t Copy & Paste. Retype.

Posted on Sat 03 October 2015 in Programming • Tagged with problem solving, Stack Overflow, typingLeave a comment

In this day and age, Google and Stack Overflow are quite essential tools for any developer. Lately, though, the latter seems to be getting some bad rap. On one side, it’s because of seemingly peculiar and sometimes alienating moderation policies. But more pertinently, it’s the apparent rise of a phenomenon that’s wittily dubbed “the full Stack Overflow developer“.

In a nutshell, individuals deserving to be called that are code slingers who throw software artifacts together mostly by copying and pasting code samples found in Stack Overflow answers. They may be getting something working pretty quickly, but they also lack understanding of problems they’re facing and solutions they’re using so cheerily.

Of course, not every instance of code Copy Pasta is to be scorned. I’m pretty sure most people reading this post (and certainly the person writing it!) are guilty of replicating at least a few snippets from Stack Overflow, verbatim, in their own codebase. Heck, we may have even done so with nigh zero interest as to why it has been written this way. Not every technology is intrinsically fascinating, after all, and deadlines are sometimes too close for comfort.

But if so, does it mean we are gradually turning into full Stack Overflow developers?… Yikes! Surely we don’t want that to happen!

Mitigation tactic

Before you shut off your Internet connection altogether while coding, consider employing the following technique whenever you feel like scraping a piece of code from Stack Overflow, and dumping it in your project source.

Don’t use the clipboard. Don’t copy and paste. Retype the code you’ve found instead.

It’s going to take more time, yes. It’s definitely more cumbersome than just hitting Ctrl+C/Ctrl+V. It may also make little sense: if the end result is the same, why does it matter whether the code was transfered through the clipboard or not?

Rationale

I’d argue, however, that it makes perfect sense. From the least to the most important, the reasons why I think so are the following:

  • The fact that retyping is slower than copy-pasting is what actually makes it better. If you vow not to use the clipboard, you’re much less likely to just pick whatever’s the first Stack Overflow result Google has given. You’ll weigh different solutions, and you’ll be rightfully biased towards shorter and simpler ones.

  • When you type something, you cannot do it completely thoughtlessly. Whether you want it or not, you’ll absorb some of the knowledge through sheer osmosis, because the code will flow through your eyes and fingers as it’s transfered from the browser to your editor or IDE. Your subconscious brain will latch onto the bits and pieces of information, and it will sort them out for you to use later. Even if you didn’t intend to, you will most likely learn something.

  • But most importantly, what you type almost certainly won’t be a perfect copy of the original snippet. As you progress through the code, you’ll inevitably deviate from it, if only to conform to a particular style guide your project is following.
    It’s quite likely, though, that you’ll make larger changes as well. You will replace familiar patterns with calls to utility functions. You’ll rearrange the code visually for better readability. You will add comments, or extract functions to make it more self-documenting. You might even enhance and customize it, so that you can abstract and reuse it multiple times.

Afterwards, what you’ve just typed won’t be just some code you have found on the Internet. It’ll be your code.

Continue reading