A common pattern in Erlang is to do some work on a list and accumulate results in "reverse order":

do_work(List) ->
    do_work(List, []).

do_work([], Acc) ->
    Acc;
do_work([Head | Tail], Acc) ->
    Result = do_something(Head),
    do_work(Tail, [Result | Acc]).

If you want to preserve the ordering of the input list, you need to reverse the accumulator before return:

do_work([], Acc) ->
    lists:reverse(Acc);

A question that comes up (in this case on #erlang today) is how well lists:reverse/1 performs: when should we reach for another data structure?

Because this pattern is so common, lists:reverse/2, which lists:reverse/1 is written in terms of, is a BIF: definition in C (note that a pile of other list functions are defined in C in the same file).

This means it should run pretty fast. The Erlang efficiency guide mentions it in the context of tail recursion, but urges us to measure.

I did some simple measurement on an old Xeon E5620 running Linux:

-module(reverse_bench).
-export([run/0]).

run() ->
    Steps = [10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000],
    Sequences = [{N, lists:seq(1, N)} || N <- Steps],
    Timings = [{N, avg_reverse_timing(Seq, 100)} || {N, Seq} <- Sequences],
    io:format("~p~n", [Timings]).

avg_reverse_timing(List, N) ->
    Timings = repeat_tc(lists, reverse, [List], N, []),
    lists:sum(Timings) / length(Timings).

repeat_tc(_, _, _, 0, Acc) ->
    Acc;
repeat_tc(M, F, A, N, Acc) ->
    {Timing, _} = timer:tc(M, F, A),
    repeat_tc(M, F, A, N - 1, [Timing | Acc]).

and graphed it with the Google Charts API:

.

Some log scales here, but as you can see, our list needs to be 100,000 elements before we hit 10ms average on this system: assuming we're doing something interesting when we process each list element, lists:reverse/1 is unlikely to dominate our runtime. Besides, since we mostly work with much smaller lists in real programs, this is definitely in the realm of "don't worry".

It's not super-scientific, but the simple answer to when to reach for something other than a list appears to be "not quickly." :o) Good luck, and measure: even naive measurement beats guessing.

I've been working with Erlang for the last quarter, and since we very much eat our own monitoring dogfood at Hosted Graphite, I've been exporting application and VM metrics from my software.

Exometer is a nicely designed monitoring library for Erlang which includes easy export to Graphite, so it's what I've been using.

The question of getting started with it seems to come up a bit on #erlang, so I've packaged up a simple library application:

basic_metrics

Rather than using exometer's static configuration options, we build everything dynamically in the module. It's a little verbose as a result, but clear and self-contained. The exports there should also provide examples for your own application metrics.

This library depends upon and uses Fred Hébert's recon for additional metrics useful in production. See also Erlang in Anger.

The exometer integration is based on Brian Troutwine's notes in Monitoring with Exometer: An Ongoing Love Story. For lots more detail on using exometer, see that article and the exometer documentation.

Brian also has a great talk online covering some of the same details: video, slides.

• Epidemic broadcast trees - Leitâo et al.

  This came up in the context of Riak scalability; IIUC it's part of the 2.0 series. Basho have report from RICON 2013 on this.

  Plumtree: "push-lazy-push multicast tree."

  Combines an eager gossip push strategy (along the spanning tree path) with a lazy gossip pull strategy (for recovery). You have a gossip overlay network (where each node has a partial view of the whole set), and a tree of nodes built on top of that. Cuts in the tree can be healed quickly by using the underlying (pull) network.

  "The links used for eager push are selected in such a way that their closure effectively builds a broadcast tree embedded in the random overlay network."

  Heh, GRAFT and PRUNE messages. :o)

  They include detailed descriptions of simulations backing up their claims.

  Abstract:

  "There is an inherent trade-off between epidemic and deterministic tree-based broadcast primitives. Tree-based approaches have a small message complexity in steady-state but are very fragile in the presence of faults. Gossip, or epidemic, protocols have a higher message complexity but also offer much higher resilience. This paper proposes an integrated broadcast scheme that combines both approaches. We use a low cost scheme to build and maintain broadcast trees embedded on a gossip-based overlay. The protocol sends the message payload preferably via tree branches but uses the remaining links of the gossip overlay for fast recovery and expedite tree healing. Experimental evaluation presented in the paper shows that our new strategy has a low overhead and that is able to support large number of faults while maintaining a high reliability."

• Software Testing with QuickCheck - John Hughes

  I'm working with Erlang these days, so I've been able to get an evaluation license for Erlang QuickCheck.

  This paper is a tutorial, working from simple property-based tests through to testing properties of a stateful system using abstract state machines to model its behaviour.

  It's lucidly written: in tandem with the QuickCheck library documentation, I was able to work fairly confidently through the examples and most of the exercises, despite the work requiring the occasional brain-flip.

  I'm really enjoying the property-based testing approach, and this implementation has clearly had a lot of work and thought put into it. It feels like cheating to be able to do testing that feels so (executably!) formal and complete in this little code.

• AQD: Remembrancer | booktwo.org

  "A Quite Disposition" is James Bridle's "weak AI for gathering information about drones". It's a fascinating project. The Remembrancer is a free newspaper built automatically from the database.

  "In this world, we must take responsibility not only for our own actions, but the actions of the vast non-human assemblages we have built around us—from corporations to complex software systems—and acknowledge the moral and physical limits of our technologies, and ourselves."

Generated from pinboard by pinroll.

Some news: I will start writing code for Hosted Graphite next week.

It's a (mostly) remote position, which makes it possible for me to spend winter in France with the family. We found a lovely place to live in an old medieval town on the Vienne. Spinning up a little French fluency now, remarkable how fast it comes when you've got a definite goal. :o)

Hat-tip (as is often the case!) to taint.org for the first two links below.

• Coreutils viewer

  Clever!

  A Linux tool to show progress for cp, rm, dd, ...

  It simply scans /proc for interesting commands, and then uses the fd/ and fdinfo/ directories to find opened files and seek position, and reports status for the biggest file.

• In Search of an Understandable Consensus Algorithm - Diego Ongaro and John Ousterhout, Stanford University

  A great read. Lucid description of the replicated state machine problem, issues with Paxos, and how Raft works. Interesting that the primary goal was understandability. Maybe that should be the case for all software and algorithms ...

• There's Just No Getting around It: You're Building a Distributed System - Mark Cavage, Joyent

  Good worked example of basic requirements & back-of-the-envelope work for an image resizing service. Separation of services, API-focused design: familiar approach.

  "the goal is simply to highlight the realities and look at the basics required to build a distributed system... Too many applications are being built by stringing together a distributed database system with some form of application, and hoping for the best."

  "Drawing parallels to a previous generation, services are the new process; they are the correct abstraction level for any discrete functionality in a system."

Generated from pinboard by pinroll.

On holiday in France. It's nice here!

• Postel's Principle is a Bad Idea. - programming is terrible

  Lots of interesting references here, and memorable quotes (as is often the way with tef's posts).

  "If some data means two different things to different parts of your program or network, it can be exploited - Interoperability is achieved at the expense of security."

  Examples from the Perl/C interface, TCP/IP, confused deputy, XSS.

  "Notably, HTML5 gained a standardized parser, not for security reasons, but to ensure that bad HTML looks the same on every browser."

  "Interoperability doesn't just mean working in the same way, but failing in the same way too."

• How To Design A Good API and Why it Matters - Joshua Bloch

  Sensible notes on API design from someone who has very much been in the trenches.

  • Public APIs are forever: one chance to get it right.
  • Make it easy to do the right thing, difficult to the wrong thing, easy to evolve.
  • Just powerful enough to satisfy requirements.
  • Gather requirements, and make a 1-page spec. Share. Pretend to code against it. Take example programs very seriously.
  • Aim to displease everyone equally.
  • Do one thing and do it well. Good names drive development.
  • When in doubt, leave it out.
  • Don't let implementation details "leak" into API. Design serialized forms carefully.
  • Minimize accessibility of everything.
  • Documentation matters. Document everything in your public API.
  • Bad decisions can limit performance; but don't warp the API to gain performance. Good design usually coincides with good performance.
  • API must coexist peacefully with the platform: transliterated APIs are almost always broken.
  • Minimize mutability. Prefer immutable; if mutable, keep state space small & well-defined.
  • Don't make the client do anything the module could - reduce boilerplate.
  • Don't violate the principle of least astonishment.
  • Provide programmatic access to all data available in string form!
  • Use consistent parameter ordering across methods.
  • Avoid return values that demand exceptional processing (e.g. return an empty collection instead of not_found).

• Actually using ed - Arabesque

  Cute tutorial on using ed. Fun to work through. There's a lot of other interesting stuff at this site, e.g. the "Unix as IDE" series.

• Nine Nines Article: Erlang Scalability

  A set of notes on things that may limit an Erlang system's scalability:

  • Avoid NIFs if possible; e.g. use MessagePack rather than JSON;
  • Be careful what BIFs you use (example of erlang:decode_packet/3 in Cowboy);
  • Use binaries rather than lists, including for buffering/streaming;
  • Don't hesitate to create a custom pool of processes to do what a single gen_server might; similarly, a custom supervisor might sometimes be the right thing.
  • Use ets public or protected tables for LOLSPEED(tm).

• How Stacks are Handled in Go - Daniel Morsing

  Clearly-written details of how goroutine stacks work (and how they soon will).

  Now: "segmented" stacks grow by allocating new segments with accounting information to find the previous outgrown. This can cause a "hot split" issue where the stack keeps growing and shrinking at the segment boundary, and releasing the new stack segment each time is expensive.

  Soon: "stack copying" creates a new segment double the size, and copies the old data to it. There's some accounting work that needs to be done here for pointers to stack data, and the Go devs are currently rewriting a pile of the runtime in Go to make this doable.

  This will also enable concurrent garbage collection in future - something which really helps in Erlang - though there are open issues with how this will work for shared heap objects in Go. I tend to prefer the Erlang shared-nothing approach ...

Generated from pinboard by pinroll.