The Intellectual Wilderness On Government: "There is nothing more useless than doing efficiently that which should not be done at all."

2016.02.2 23:51

zUUID: An Example Erlang/OTP Project

Filed under: Computing — Tags: , , , , , , — zxq9 @ 23:51

I was talking with a friend of mine yesterday about how UUID v2 seems to have evaporated. We looked into things further and found its not actually included in RFC 4122! One thing led to another and I wound up writing an example project that is yet another UUID generator/utility in Erlang — but this time it actually has duplicate v1 and v2 detection/correction and implements as close to what I can find is defined as UUID version 2 values.

As there are already plenty of UUID projects around I focused on making this one as readable as I possibly could — to include exported documentation, in-source documentation, obvious variable names, full typespecs, my silly little “pure” notation, blatantly obvious bitstring syntax, and the obligatory github presence.

Hopefully some folks newish to Erlang will come along and explain to me what confuses them about that code, the process of writing it, the documentation conventions, etc. so that I can become a better literate programmer. Of course, since the last thing the world needs is another UUID implementation I suppose I would have had better luck with something at least peripherally related to the web. (>.<)

2016.01.21 11:59

Erlang R18.0 Docs

Filed under: Computing — Tags: , , , — zxq9 @ 11:59

Language sites get knocked offline from time to time, so in addition to the Guile 2. manual I also keep a mirror of the Erlang R18 docs. I’ve never needed to link to them from here, but today has been a rough day around the internet for some reason so here we are. Depending on how long they stay down I might add the latest revision as well.

2016.01.20 16:59

Messaging: What Will It Do?

[Part 2 of a short series on messaging systems. (Part 1)]

Having implemented messaging systems of various sizes and scopes in all sorts of environments, I’ve come up with a few guidelines for myself:

  1. If messaging is not the core service, make it an orthogonal network service.
  2. If possible make the messages ephemeral.
  3. If the messages must persist use the lightest storage solution possible and store as little as possible.
  4. Accept that huge message traffic will mean partitioning, partitions will be eventually consistent, and this is OK.
  5. You don’t need full text search.
  6. If you really do need full text search then use a DB that is built for this — its a major time-sink to hack it in later and get it right.
  7. If the messages are threaded annotations over other existing relational data, swallow your pride and consult your DBA.
  8. VERSION. Your. DATA. And. PROTOCOLS.
  9. If anything about messages over existing data records feels hacky, awkward, or like it might put pressure on the existing DB, separate message storage and accept that some data integrity may be delayed or lost from time to time.
  10. Messaging is likely more important to your users than you (or they) think it is.
  11. The messages themselves are likely less important to your users than you (or they) think they are.
  12. If you can skip a feature, DO.
  13. YAGNI.
  14. You don’t need [AdvancedMessagingProtocol] (aka XMPP).
  15. If you *really* need XMPP it will be painfully obvious (and if you do chances are you certainly don’t need the extensions).
  16. [insert more things about avoiding feature creep]

Adding messaging to an existing system can get a little messy if you’re not really sure why you are doing it. If you know that your users really do have a need for messaging within your system, but you don’t know what features or type of messaging it should be, then think carefully about how you would want to use it as a user yourself.

Do users work together within your system to accomplish immediate goals? A concurrent multiuser system (multiplayer game, concurrent design tool, pair programming environment, etc.) benefits most from an ephemeral, instant chat system that centers around the immediate task. When the task is over the messages become meaningless and should be allowed to decay. It may be nice to give users an easy way to export or save significant messages, but that is really a client-side issue and is orthogonal to how the messaging system itself works.

Is the system used to coordinate real-world tasks or events? A real-world coordination system benefits most from a threaded comment/discussion system that centers around those tasks, and must only enhance but not replace the existing task-assignment and tracking features of the system. Threaded annotation is powerful here, but the threads need only persist as long as the task records do and messaging should never be mistaken for a task assignment tool (it can be leveraged as a part of task notification but never assignment or tracking). Remember ON DELETE CASCADE? This is where it is super helpful.

Do users self-organize into groups whose sole purpose is communication? Social group systems benefit most from mail systems implemented directly within the system they use to organize themselves. Such systems may also benefit from some form of ephemeral immediate chat, but it is critical that we keep in mind that that indicates a need for two different messaging systems, not One Message System To Rule Them All.

Many different flavors of message systems exist between the extremes of “persistent point-to-point mail” and “ephemeral, instant, channelized (group) chat”. Consider:

  • Persistent chat (Campfire, SocialObstructionist StackOverflow chat, etc.))
  • Message boards (“forums” — though this term is far broader in actual meaning…)
  • Usenet-style newsgroups
  • Mailing list systems
  • Email bridges
  • IRC + bridges + bots
  • Anything else you can imagine…

Some other things to think about are the nature of the users relationship to one another. That’s not just about communication channels and point-to-point delivery issues, it is also about what concept of identity exists within the system. Is the system one with strong authentication, total or partial anonymity, or a hybrid? This will dictate everything about your approach to permissions — from moderation, channel creation and administrative control to whether private messages are permissible and have a huge impact on what the implementation of a messaging system will require in terms of access to the original host system it is intended to support.

The issues of identity, authentication and public visibility are largely orthogonal to questions of persistence duration, storage and message-to-record relationship, but they can become intertwined issues without you realizing it whenever it comes time to design the storage schema, the serialization format(s), or the protocol(s). Of course these are three flavors of basically the same issue — though the modern trend is shy away from thinking about this either by hiding behind HTTP (like, uh, who even knows how to program sockets anymore? zomg!) and sticking your fingers in your ears when someone says that “schemaless JSON is the schema” or that XML can do the job of all three because it is the pinnacle of data representations. Consider whether this may change in the future. Keep YAGNI in mind, but when it comes to schemas, serialization and protocols it is always good to design something that can be extended without requiring core modification.

Messaging: Why Would You Do This?

[Part 1 of a short series on messaging systems. (Part 2)]

Messaging is a feature that seems to wind up on the ZOMG MUST HAVE!!1! feature list long after initial system deployment quite a bit these days. I’ve been getting asked about this a lot lately, so I’ve written down my generic advice here for reference. (If you want more specific advice feel free to contact me, though — its interesting and fun to hear about all the different things people are working on.)

I’ve been implementing and deploying messaging systems in one form or another since I first got involved with computers as a kid in the very late 80’s and early 90’s. Back then most multiplayer games were basically text message dispatch and routing systems with thematic computation surrounding those messages, so this was an area quite a few people my age dealt with — without realizing that it would one day be considered an “enterprise” feature. (And to think, we used to do this in Pascal, and assembler, and C, and hilariously inadequate variants of BASIC… as children! That nonsense was only reasonable to us because they were the only tools we had, those were labors of love, and we didn’t know any better.)

The most important thing to recognize about messaging systems is that the term “messaging” is hopelessly broad. It doesn’t really mean anything by itself. Every over-the-wire protocol is a message system definition, for example. Every drop-it-in-a-spool system is also a messaging system. Every combat notification system in a game is a messaging system. Every websocket thing you’ve ever done is a messaging system. This list could go on for quite a while, but I assume you get the idea.

Messaging systems take on different characteristics depending on their context of use. Some messaging systems are persistent, some are ephemeral, some have selective decay, some are instant, some are asynch, some are channeled, some are global, some are private, some are selective-access, some are moderated, some include extra semantic data that can be interpreted in the message body, some run everything through a central data service (“ooooh, ahhhh, ‘the cloud'”), some are peered, some are anonymous, some are verified, some broadcast, some are point to point, some are free, some are paid in per-message increments, some are paid by aggregate use, etc. The list keeps going as long as you can think of things that can be said about any system, actually.

It is important to keep in mind that most of the adjectives in the last paragraph are not mutually exclusive. Here is the fun part, though: if you need two that are, then you need two messaging systems. (That’s why they make chocolate and vanilla, after all.)

That’s a lot of different aspects to something as conceptually simple as “messaging”. The obvious problem there is that messaging is actually not simple at all in practice. When you decide that you need a “messaging solution” you really must carefully consider what that means for your users and your system. Your users’ state of mind, user experience, utility value of messaging and desire to use messaging in the context of their use of your system are all folded together.

Consider this: Email is a messaging system and we’ve all already got that, why is this not sufficient for your use? If you can’t answer that question quickly then sit back and let it stew for a bit — you will learn something about your users in the process of answering this question because it forces you to think for a moment as a user of your system instead of as a builder of it.

Let’s consider some reasons you might want to add a killer messaging feature to your existing product or system.

  • You can’t figure out the difference between “organic pageviews” and traffic resulting from the robot invasion.
  • You want more pageviews and you don’t care how you get them — messaging, you think, can be a source of bajillions of clicks!
  • Your users deal with data objects about which they constantly converse, but can’t do so within your system.
  • Your users have things to express that are best represented in a way that captures the history of their thoughts in sequence.
  • Your native applications do exactly what they should, but breaking out of it to send a message is distracting.
  • Your system already passes data among users, but requires human annotation to be fully meaningful.
  • Your system deals in machine-to-machine messages already, but users still have to call each other on the phone.
  • You are looking for a way to attach your brand to one more thing users see every day to reinforce the hypnotic effect you wish your brand had on them.
  • You require an anonymous(ish) way for users to communicate out-of-band relative to other online services.

A conditional flow would look something like this:

stupid_reasons = [pageviews,
                  domain_valuation,
                  brand_enhancement,
                  pagerank,
                  BULLSHIT_WEB_IDEAS(SEO && ALL_FLAGS),
                  ADS([ad_search, ad_rank, ad_tech, ad_{*}, ...]),
                  ...];

if (member(your_reason, stupid_reasons)) {
    if (idea_of(You) || you_are(TheManagement)) {
        admit(being_wrong);
        assert cancer_killing_internet = You;
        abort(stupid_idea);
        quick_grieve(dying_product);
    } else if (idea_of(TheManagement)) {
        abort(current_job, GRACEFULLY);
        // It won't last much longer anyway.
    }
    acquire(funding_contacts);
    contact(me, IRL);
    // I've got way better ideas.
    // You should work with me instead of sticking with losers.
} else if (knee_jerk(messaging_feature)) {
    abort(stupid_idea);
    focus(core_features);
} else {
    congratulate(You);
    panic(FEATURE_BURDEN);
    CAREFULLY(implement());
}

quick_grieve(hopeless_thing)
{
    shock(hopeless_thing, DEAD);
    anger(cant_coerce([model, users, investors, world]),
          TANTRUM_LEVEL(11));
    bargain([me, you, imaginary_entities, investors, users, world, HAL],
            perceived_value(hopeless_thing, PERSPECTIVE(MYOPIC)));
    mourn(hopeless_thing);
    accept(DEFEAT);

    return AGGRESSIVE_OUTLOOK([POSITIVE && EXPERIENCED]);
}

Did you find yourself at congratulations(), or somewhere else? Stop and think for a while if your reason belongs in the stupid_reasons list or not. How much will it actually enhance your users’ experience with the product or interaction with each other or you? Are you going to use it yourself, or are you going to continue to use email, IRC, whatever corporate chat service is popular this week, Twitter, etc? (And if you say “Well, I/we don’t use my/our product, so I don’t know…” then you are already rather far beyond admitting defeat, you just don’t know it yet.)

Be painfully honest with yourself here because messaging is one of those things that you can’t add in and then just take away later without consequences. Even if very few people use it and it turns out to be a technical burden to you someone will wind up using it no matter how shitty it turns out to actually be, a few of these people will come to depend on it, and to these people you will be an asshole if you ever remove it. Don’t be an asshole to customers. That’s how you wind up with a “[your_product]sucks.com” — and the kind of users who come to depend on weird internal messaging systems that suck are exactly the kind of people who will register a domain like that and talk shit about you. That crap will stay on the web forever and the stink may stay on your product forever, even if you change your product and they come back loving it.

So let’s assume that your system will exist in a context where it really does add value to the user’s life in some way. goto congratulations()! Messaging will be a big win if done properly and unobtrusively. As a reward for being diligent and thoughtful you now you get to wade through a swamp of design issues. But don’t worry, I’ll give you the fanboat tour and point the way through the muck.

Next we’ll look at some common features of messaging systems, what they mean for your implementation and most importantly what they mean for your users within the context of your system. [Continue to Part 2]

2015.12.21 19:38

Pure Declarations in Erlang

Over the last year or so I’ve gone back and forth in my mind and in discussions with other Erlangers about type systems in Erlang, or rather, I’ve been going back and forth about its lack of one and the way Dialyzer acts as our bandaid in this area. Types are useful enough that we need Dialyzer, but the pursuit of functional puritanism gets insane enough that its simply not worth it in a language intended for real-world production use, especially in the messy, massively concurrent, let-it-crash, side-effecty, message-centric world of Erlang.

But… types and pure functions are still really useful and setting a goal of making as much of a program as possible into provable, bounded, typed, pure functions tends to result in easy to understand, test and maintain code. So there is obviously some stress here.

What I would like to do is add a semantic that the compiler (or Dialyzer, but would prefer this be a compiler check, tbh) be aware of what functions are pure and which are not. The way I would do this is by using a different “arrow”, in particular the Prolog-style declaration indicator: :-

[Edit after further discussion…] What I would like to do is add a directive that Dialyzer can interpret according to a simply purity rule. Adding this to Dialyzer makes more sense than putting it in the compiler — Dialyzer is already concerned with checking; the compiler is already concerned with compiling.

The directive would be -pure(Name/Arity) (a compliment to -spec). The rule would be very simple: only guard-permissible BIFs and other pure functions are legal from within the body of a pure function. This is basically just an extension of the current guard rule (actually, I wonder why this version isn’t already the guard rule… other than the fact that unless something like this is implemented the compiler itself wouldn’t have any way of checking for purity, so currently it must blindly accept a handful of BIFs known to be pure and nothing else).

For example, here is a pure function in Erlang, but neither the compiler nor Dialyzer can currently know this:

-spec increment(integer()) -> integer().
increment(A) ->
    A + 1.

Here is the same function declared to be pure:

-pure(increment/1).
-spec increment(integer()) -> integer().
increment(A) ->
    A + 1.

Pretty simple change.

“ZOMG! The whold standard library!” And yes, this is true — the whole thing is out. Except that the most important bits of it (the data structures like lists, dict, maps, etc.) could be easily converted to pure functions with little more than changing -> to :- adding a single line to the definition.

Any pure function could be strongly typed and Dialyzer could adhere to strong types instead of looser “success types” in these cases. Some code that is currently written to take an input from a side-effecty function, pass it through a chain of non-returning and possible side-effecty functions as a way to process or act on the value, and ultimately then call some side-effecty final output function would instead change to a form where the side-effects are limited to a single function that does both the input and output, and all the processing in-between would be done in pure functions.

This makes code inherently more testable. In the first case any test of the code is essentially an integration test — as to really know how things will work requires knowing at least one step into side effects (and very often we litter our code with side-effects without a second thought, something prayer-style monadisms assist greatly with). In the second case, though, the majority of the program is pure and independently testable, with no passthrough chain of values that have to be checked. I would argue that in many cases such passthrough is either totally unnecessary, or when it really is beneficial passing through in functions is not as useful as passing through in processes — that is to say, that when transformational passthrough is desired it is easier to reason about an Erlang program as a series of signal transformations over a message stream than a chain of arbitrarily side-effecty function calls that collectively make a recursive tail-call (and that’s a whole different ball of wax, totally orthogonal to the issue of functional purity).

Consider what we can know about a basic receive loop:

loop(State) ->
  receive
    {process, Data} ->
        {ok, NewState} = do_process(Data, State),
        loop(NewState);
    {send_state, From} ->
        From ! State,
        loop(State);
    halt ->
        exit(normal);
    Message ->
        ok = log(unexpected, Unexpected),
        loop(State)
  end.

-spec do_process(term(), #state{}) -> {ok, #state{}} | {error, term()}.
do_process(Data, State) :-
    % Do purely functional stuff
    Result.

-spec log(category(), term()) -> ok.
log(Cat, Data) ->
    % Do side-effecty stuff
    ok.

We can see exactly what cases result in another iteration and which don’t. Compare that with this:

loop(State) ->
  receive
    {process, Data}     -> do_process(Data, State);
    {send_state, Asker} -> tell(Asker, State);
    quit                -> exit(normal);
    Message             -> handle_unexpected(Message, State)
  end.

do_process(Data, State) ->
    % Do stuff.
    % Mutually recursive tail call; no return type.
    loop(NewState).

tell(Asker, State) ->
    % Do stuff; another tail call...
    loop(State).

handle_unexpected(Message, State) ->
    ok = log(unexpected, Message),
    % Do whatever else; end with tail call to loop/1...
    loop(NewState).

I like the way the code lines up visually in the last version of loop/1, sure, but I can’t know nearly as much about it as a process. Both styles are common, but the former lends itself to readability and testing while the latter is a real mixed bag. Pure functions would keep us conscious of what we are doing and commit our minds in ways to the definite-return form of code where our pure functions and our side-effecty ones are clearly separated. Of course, anyone could also continue to write Erlang any old way they used to — this would just be one more tool to assist with breaking complexity down and adding some compile-time checking in large systems.

I would love to see this sort of thing happen within Erlang eventually, but I am pretty certain that its the sort of change that won’t happen if I don’t roll up my sleeves and do it myself. We’ve got bigger fish to fry, in my opinion, (and I’ve certainly got higher priorities personally right now!) but perhaps someday…

2015.12.8 23:31

Rich Hickey: Simple Made Easy

Filed under: Computing,Overlooked Resources — zxq9 @ 23:31

This is an excellent presentation of the “soft tech talk” type given by Rich Hickey about the difference between a thing being “easy” in the sense that it is near to our experience and it actually being “simple” in the sense that understanding the idea does not force us to understand a lot of other ideas that are partially folded into it. His point is that we should be careful about the way we use the words “easy” and “simple” and be rather more specific than we tend to be, because this hides up a rather large and common class of complexity problems that we tend to gloss over within programmer society because we are merely familiar with a huge class of unnecessarily complicated constructs that have nothing to do with the business problems we are supposed to be solving.

Rich Hickey: Simple Made Easy

If only it were glaringly obvious to us when we were engaging in the glossing-over of non-essential complexity in architecture. I suppose one way of at least trying to become conscious of this is the frequency of use of a certain alarm-bell phrase: “just”. Ward Cunningham’s wiki actually has a whole page on it, along with another page that enumerates and discusses/argues a few other linguistic red flags of note.

2015.11.30 17:29

How the Internet of Things Will Change the World: Not by Much

Are you ready for the enormous, revolutionary, ground-shattering changes coming with the IoT?

If you said “yes” and by “yes” you meant you were prepared for breathtaking changes, you are a naive child wading in a murky pool of lampreys, your will putty in the hands of the same charlatans who brought you terms like “cloud computing” which still has yet to be defined in any concrete technical sense.

If you said “yes” and by “yes” you meant that you felt that the more things change the more they stay the same — then you are indeed prepared.

Cold War II, civil war in China, the breakup of the EU, abolishment of American drug laws, the DEA and an end to the Mexican civil war all at once — those are the kinds of things that will have a measurable impact on life. The so-called “internet of things” concept as heard in internet marketing is… well, not at all what the guy who coined the term “Internet of Things” meant.

We already have an internet of things. Has it cured cancer yet? Nope. But if we put RFID in every part of our bodies we will certainly be even more exposed to the will of outside actors. Not that the public has demonstrated that it cares about complete loss of its privacy, especially when “Google style conveniences in exchange for your life’s data” can be backed up by the rhetoric of fear necessitated by government “anti-terrorism” funding. (Yes, I mock this, and yes, I was a Green Beret in the US Army for 6 years — the direction that rhetoric is headed is toward government empowerment, and the government is exactly the least well equipped element of society to deal with terrorism.)

Want to see an internet of things? Tesla cars receive system updates across the network now, and can turn in performance data to help the maker improve on their designs and software. Open water jetski robots can follow automated routes and report hydrographic and bathyrithmic data back to a data processing facility to chart change over time. I was working on a (now defunct, but promising) design project to develop spotting scopes that were intelligent enough to peer data amongst one another within an operational space and change “spotter calls” into more generally interesting “shot requests” and aggregate shot providers in the area to engage targets based on type, effect and following damage reports. Whenever any peers had a network connection they could aggregate data externally.

Dude, we’re already there.

What we lack is standards. Oh, wait, nevermind… we actually have tens of thousands of those. What we lack is standards that people actually can use, that aren’t harder to learn and comply with than the handling of the basic user problems at hand are. These problems will mostly never be solved, not really. Truly understandable data must have a semantic foundation, and semantics are essentially arbitrary in most ways that matter in data processing. That means data must either be tagged in a non-trivial way or must be placed into a schema where relationships are what have meanings.

Note that “tagged in a non-trivial way” above means taking tagging systems to such extremes that they become their own ontologies. Think about that. It should make your face turn pale. That’s at least as difficult as developing an arbitrary formal language — and in case you didn’t notice, an “arbitrary formal” language is a oxymoron. Writing even trivial software using such a tagging system would require that programmers at every step of the system learn this arbitrary formal language of tagging before they do much of anything, and that’s a lot harder overall than just continuing on with our pile-of-ad-hoc-systems approach. Schema-based systems, while having some different tradeoffs (computationally natural descriptions of data as a “shape”, for example, is a really big win in practical application), ultimately suffer from the same complexity explosion at some level. In particular, applying a particular schema designed in the context of one problem domain will very often not fit in the context of another problem domain — and fully normalizing all data ever, ever would eventually require an infinite (and ever growing) number of relational definitions. Yech.

So… Internet of things? Yeah. We’re already living it. Don’t get too excited and don’t give into the hype. Just because you technically can read data from remote sensors or activate your house’s appliances with your phone (hint: you already can) doesn’t mean this is something you will want to do, or that the venture capitalists of the world will peel their lips off the adsearch cock for long enough to realize that there are more interesting things they could be funding than bounce-under ads and invisible iframe reclick-to-click javascript tech.

Rest easy. Humanity’s material circumstances will continue to get incrementally better (save the occasional dip due to predictably stupid things we do to ourselves) until The Singularity when we are all either suddenly eliminated due to obsolescence, or drive ourselves into a new mode of existence-as-slavery to whatever Google turns into (when all data is network accessible, privacy does not exist, all data is the private IP of a single aggregate, the rights of conscious uploaded entities don’t exist, the definition of “life” is still “way way way after birth”, and continued conscious existence equates to paying a service charge — that’s not really life). None of this is particularly dependent upon the hype surrounding the “Internet of Things”.

Almost Always Stupid: Parallel Quicksort

So you’ve been thinking about applying your awesome parallel programming skills to some problem that is just complex enough to impress the noobs, but just trivial enough to code in a few lines? Cool. Knock yourself out.

But stop trying to parallelize quicksort.

Posting articles, tutorials, SO questions, and blog posts with the term “parallel quicksort” in the title only serves to encourage excitable, well-meaning, naive people to copypasta whatever code they find there and screw up what would have otherwise been straightforward, easy-to-read, relatively performant beginner-style code.

A naive quicksort implementation is pretty darn fast in the common cases found in real programs. There are edge cases where an intelligently chosen pivot can be a significant optimization — but the act of choosing the pivot intelligently is not free, which means before committing to this you have to know a lot about the context in which that particular sort will be used so you can be confident that it won’t be an overall pessimization.

A naive parallel quicksort implementation can only ever be slower than a naive serialized quicksort. Why? Think through the serial algorithm: each branch depends on the results of the subsequent branches. When we parallelize that the same dependencies exist but you’ve added the overhead of spawning and messaging to the rollup of values at the end. Even in Erlang where spawning and messaging (on a single node) are amazingly lighter weight and faster than in other environments, spawning and messaging are still more overhead in terms of time and memory than simple comparison. So a naive parallelized quicksort, while perhaps impressive because you get to show that you’re spawning and messaging everywhere, is never going to be as fast as a normal naive quicksort.

What about an intelligent parallel quicksort? Ah. Now here we have something potentially interesting. This can indeed be a significant performance win, even bigger than the case of an intelligently implemented quicksort in a guaranteed case of lopsided values where you know where the optimal pivot is located (consider for a moment how utterly tailored to the situation the choice must be, and how utterly familiar with things about that specific use case that are not quicksort one must be to know that any of this is true).

Let’s assume everything is going your way and you can already have a lot of information about the list you need to sort — enough that the overhead of finding smart pivots is outweighed by the overall running time of the sort — it can indeed be possible to write a much faster parallel sort. But not by forking more workers than you have schedulers.

The naive parallel quicksort forks/spawns every branch. That’s insane. A smart parallel quicksort will only fork until it has occupied the available scheduling resources of the system (cores, threads, schedulers, whatever the environment has). Why? Because forking any further will only incur scheduling overhead that amounts to busywork the platform has to do just to keep up with multiprocess accounting. That means an intelligent parallel quicksort will have to know not only how to pick an optimum pivot, it will also have to know how to stop forking once it has maxed out the scheduling resources of the system, and it will have to pull one more not-so-simple trick: it will have to know enough about the data being sorted to continue picking smart pivots until it is finished forking (to be faster than a simply paritioned two-threaded implementation).

That is a significant amount of arcane information needed about the input, and a not entirely obvious pile of code needed to both continue to pick pivots, communicate among threads and stop forking once the optimum number of threads for the environment has been reached. I know how to find out how many schedulers are available in an Erlang node, and I know how to find out how many cores are available on a Linux or BSD system in C. I don’t know how to find this out in Go or Java. I’m not really sure how to do it in Python, either, other than just making a subprocess call — but oops, see, once I do that the code isn’t really Python, it is “Python that works on platform X” (and not to mention, most sorts will complete in less time than a call via subprocess will… defeating the point). That’s a programmer pessimization. Spending a huge amount of time to write code that by definition probably can’t be made generic and reused later is not a very intelligent use of time (neither is writing this blog post, for that matter).

What else happens, though, when we parallelize quicksort? When we parallelize anything? Nothing is free, so there must be a cost. What are some cases where I want to sort things, and of those what cases are good candidates for parallel quicksort? This list isn’t exhaustive (sorting is pretty common) but thinking through the tradeoffs in just a few common situations may be illustrative. Remember: optimizations are usually tradeoffs. Once a routine has been optimized for the general case the remaining options are about shifting burdens away from dear resources and onto cheap ones (or, in the happiest case, not doing anything).

  1. Sorting a list before passing it to a function that requires a sorted list.
  2. Before an efficient update/merge of two lists (a special case of the above).
  3. Ordering client-side data for presentation.
  4. Organizing log data before flush (can be thought of  as a variation of the above).
  5. Building indexes.
  6. Organizing variable length search data (usually text search; a variant of the above).

In any of the cases above is it likely that I might have a set of data that is so huge that I might need to optimize the sort operation? Maybe in cases #1, #2, #4, #5, and very often in #6. So that’s entirely possible.

In any cases above is it likely that I will know enough to be able to build a customized parallel quicksort that is smart enough to pick smart pivots? Hrm… that is a lot trickier. Assuming you already might know something extra about the nature of the input it is maybe possible that this could be the case in #4, or #5 — but that is not the general case. You’d have to know an awful lot to get this right. The most likely candidate here is actually just #6.

Of the remaining cases (and for the vast majority of actual code, that is really just going to be #6), are there any situations where I want to slow down the whole system just to make a single sort go faster? Is the system doing anything else that might be important? Will this degrade overall performance when run in a cron job? Is perhaps the whole point of having lots of cores that maybe we don’t want the entire system to be affected by a single long-running operation? Consider a database that needs to build a text search index and pass it somewhere else based on whatever has changed in the last 12 hours (or an adsearch index builder that needs to sort billions of items of campaign change data). Is it acceptable for the whole system to experience a performance degradation? I don’t know — only you can answer that question. It might be a big win, it might not. I’ve only encountered a single case* where this was true in actual production code.

Once. Ever.

Now go do a search for “parallel quicksort” and skim over the results with new eyes. You almost never need this. Most articles on parallel quicksort are exactly as useful as the articles on parallel Fibonacci functions (or any Fibonacci functions, really). Sure, some of the code examples are fun to read and muse about, but they don’t get you any closer to solving whatever your actual user problems are.

[* Actually, it was adsearch campaign data, which is why I mentioned it.]

2015.11.15 18:24

Methodologies in open source development

Filed under: Computing — Tags: , , , , , — zxq9 @ 18:24

Prompted by an article on opensource.com about scrum in foss projects. This is an incomplete, impulsive rough draft and requires some major revisions.

Nothing makes me facepalm faster than when I get hired to work on a project and the first thing anyone tells me is “This project is going to be great because we are using the best methodologies, you know, like TDD and Scrum and everything. Totally perfect.”

WTF!? How about telling me about the problem the project solves or why it will be an improvement over whatever came before or talking about the architecture or something? There are only three conclusions I can draw from seeing that the only thing someone can think to say when I first enter a project is a word about methodology:

  1. They have no clue what the project actually does.
  2. There are no project goals.
  3. They are hiring me specifically because they have not yet encountered any other competent developers and they know it, yet (amazingly) they feel confident in dictating whatever they decided are “best practices” to me.

AHHHHHH!

Often this results in me backing out of a job, or leaving if I had tentatively agreed to it already — unless they are just going to pay enough to make watching a project tie itself in knots worth my time.

(Incidentally, I was talking with a guy from Klarna the other day and had the exact opposite experience. They know what problem their platform tackles and why it is a really good idea. So its not hopeless everywhere, just most places. What is really amazing is the guy I was speaking to wasn’t even a developer but understood what their main product is all about. That’s almost a reason to have actual hope for the future of that particular company. I don’t think I’ve written the word “hope” without prefacing it with a word like “unreasonable”, “false”, “sad” or “vain” in an article about software development.)

Today there is a problem with methodologies infecting and then blinding software projects (foss and otherwise). Its like competing flavors of ISIS taking over the ethos of various management and teams while sapping the reason from their adherents. Its not that Scrum or Agile or TDD are necessarily bad — there are a lot of good ideas that can be pulled from them — it is problematic that things like Scrum have become religions. Let’s put that in the big letters:

The problem isn’t this or that particular practice, it is the religion part.
— Me, just now

When it is absolutely unacceptable to question the utility of a methodology or specific coding practice you have a major problem. Selecting a particular set of practices without any regard to the context within which the methods or techniques are to be applied you are simply making uncritical, faith-based decisions. That is like hoping that a man who lives in the clouds will make everything better for you because you move a wooden block back and forth three times a day or kiss the ground a lot.

No, nevermind, actually it is worse than that, because you’ll only lose a few moments of your day moving a little block of wood around and kissing the ground is pretty quick. Neither has to bother anyone else who is trying to be productive right then. It is when you schedule daily or weekly meetings about block-moving techniques, force everyone to take a “vacation/working retreat” (oxymoron much?) to the tune of hundreds of thousands of dollars in company money to attend seminars given by charlatans about ground-kissing, and schedule weekend work time and “fun events” like 24-hour “hackathons” and “weekend sprints” to make up for the time lost in coordinating all the above activities. That’s way worse.

(Note that in the ranty paragraph above I’m not calling all scrum/agile/whatever coaches charlatans. The real coaches I’ve met (who have themselves written successful software) would agree entirely with what I’m writing here and tend to say straight out that chosen practices must match the context of the project. I am calling the seminar circuit and “methodology certification” guys charlatans. Those shitbags have learned that they can make crazy money by telling sweet, long, loud lies to management in a culture desperate for something to point value-blind investors at as a reason to throw good money after bad. Of course, this also implies that quite a bit of tech management is incompetent and most tech investors are just shooting in the dark.)

Without the ability to question a practice it becomes impossible to evaluate its impact on your goals. For example, sometimes TDD makes a lot of sense, especially when the product is a library. Srsly, if you write libraries and you don’t do TDD then you had better have some other word for something that amounts to the same thing. But sometimes tests — especially when they are, by necessity, integration tests of a non-trivial, comprehensive nature — can be a massive distraction, totally unhelpful, and a noticeable net loss to a project (especially project components that are literally untestable before the heat death of the universe).

The choice of a methodology or technique has to be a goal-based decision. Very often this means a business decision but sometimes its a project-goals-and-ethos type decision. Business decisions are the easiest because they are the most straightforward and the goals are relatively simple. It is a bit different in a foss project where adherence to a particular practice might be an underlying goal or a core part of the social value system that surrounds it. But even in a foss project it isn’t so hard to pin down a goal and determine how a particular practice when imposed as a rule will either help, hinder, or confuse the goal.

There is a general incongruency  between the context scrum was designed around and the context within which most foss projects exist. Scrum (and agile in general) is about customer-facing code; specifically in the case where the customer is a paying entity that is inexpert in the software being developed, but the developers are inexpert in the problem domain being solved. That is the primary Agile use case. It works well there — but this does not describe the situation of most foss projects.

Most foss projects are intended to be used by other software developers or techie users (system operators, interface specialists, DBAs, etc.), and are especially focused around infrastructure. In this case Agile simply doesn’t fit. Some documentation policies don’t even fit: there is a lot of blending among the idea that “code should be documented”, “code should be commented”, “comments should adhere to a markup that generates documentation”, “the API documentation is the manual” and “there is a product manual”. These are not at all the same things in certain markets, but in the open source world there are shades of meaning there spanning “the code is the documentation” to “literate code” to “we have a separate documentation project”.

I use foss software almost exclusively for work, but my customers don’t. They have no idea the difference, really, and don’t care over the span of a purchasing decision whether they are getting foss software or proprietary software — they only care that it works to solve their immediate business problem (that closed source sometimes introduces a different, longer-term business problem is not something they are generally prepared to understand the arguments for). In this case I have non-developer users paying for my (incidentally foss) software — and scrum/agile/whatever works very well there as a set of guidelines and practices to draw from when outlining my group’s workflow.

But the infrastructure stuff we do that sits behind all that — scrum/agile/whatever is totally insane. There is no “sit in with the customer to develop use cases” and holding a scrum meeting daily when it comes to network protocols that underlie the whole system, or the crypto suites that render the whole thing safe, or the database schemas that decompose the raw data into meanings relevant on the back-end. That sort of stuff is generally core-competency for foss developers, but it doesn’t fit the scrum or agile methodologies at all.

Only when you are working on a wicker-castle of a web project where concerns are so totally interwoven and mishmashed together that front-end customer-facing concerns become backend concerns does agile make any sense — but in this case it only makes sense because you are shipping a giant ball of mud and your hair is on fire every single day because you’ll never catch up with breakages (welcome to the actual modern paradigm that rules 90% of software projects I’ve seen…).

I’ve poked at a few different sides of development. What I’m really getting at is that there are different worlds of software development, and each world is suited better or worse by different methodologies that have been developed over time. (As an extreme case, consider the lunacy of scrum in most embedded projects.) No methodology I’ve ever seen fits any given project very well, but all of them absolutely work against the interests of a project that exists outside the context from which they originated. That could be because of time constraints (consider the infamous “docs don’t pay” attitude — yet it shouldn’t be dismissed outright because it is actually a valid business concern sometimes), the context of use doesn’t fit, or whatever.

In the same way that we (should) try to pick the best tools (languages, data stores, data structures, network paradigms, etc.) for a given job based on the nature of the task, we should approach selection of development methodology and team workflow based on the nature and context of the project.

2015.09.29 10:19

Iterators? We Don’t NEED No Stinking Iterators!

Filed under: Computing — Tags: , , , , , , — zxq9 @ 10:19

Every so often a request for “implementation of iterators for maps” over hashes/maps/dicts or some other K-V data structure appears on mailing list for a functional langauge. I’ve spent years making heavy use of iterators in imperative languages, and the way they fit into Python is really great. For Python. I totally understand where some of these folks are coming from, they just don’t realize that functional languages are not where they came from.

So… “Is this post the result of some actual event”? Yeah, you got me. It is. On the erlang-questions mailing list someone asked “Are maps ever going to get an iterator?” Again.

Erlang is definitely not Kansas, but people thinking either that it is or (more dangerously) that it should be and then trying to influence the maintainers to make it that way (and then the powers-that-be getting in a panic over “market share” and doing horrible things to the language…) worries me a bit.

There is no faster way to paint a functional language into a corner than to try making it occasionally imperative. Conversely, consider the syntactic corner C++ and Java have painted themselves into by trying to include functional features as after-thoughts where they really didn’t belong.

(I know, I know, death-by-kitchen-sink is a proud C++ tradition. It is becoming one for Java. Even though I hate Java there is no sense in making it worse by cluttering its syntax and littering it with gotchas and newbie-unfriendly readability landmines in the interest of providing features few Java coders understand the point of, especially when the whole concept of state management in a bondage-and-discipline OOP language like Java is to keep everything in structs with legs (not anonymous closures over state that is temporarily in scope…). The lack of such problems were previously one of the main points that favored Java over C++… well, that and actual encapsulation. Hopefully Rust and D can resist this temptation.)

This frustrates me. It is almost as if instead of picking a tool that matches a given job, people learn one tool and then try over time to make a super-powered Swiss Army knife of it. This never turns out well. The result is more Frankenstein’s Monster than Swiss Army knife and in the best case it winds up being hard to learn, confusing to document and crap at everything.

What’s worse, people assume that the first tool they learned well is the standard by which everything else should be judged (if so, then why are they learning anything else?). It follows, then, that if a newly studied LangX does not have a feature of previously used LangY then it must be introduced because it is “missing”. (I do admit, though, to wishing other languages had pattern matching in function heads… but I don’t bring this up on mailing lists as if its a “missing feature”; I do, however, cackle insanely when overloading is compared with matching.)

Let’s say we did include iterators for maps into Erlang — whatever an “iterator” is supposed to mean in a list-are-conses type functional language. What would that enable?

-spec foreach(fun(), map()) -> ok.

That sort of looks pointless. Its exactly the same as lists:foreach(Fun, maps:to_list(Map)) or maybe lists:foreach(Fun, maps:values(Map)). Without knowing whether we’re trying to build a new map based on the old one or get some side effect out of Fun then its hard to know what the point is.

Maybe:

-spec map(fun(), OldMap :: map()) -> {ok, NewMap :: map()}.

But… wait, isn’t that just maps:map/2 all over again?

I think I know where this is going, though. These people really wish maps were ordered dictionaries, because they want keys to be ordered. So they want something like this:

-spec side_effects_in_order_dammit(fun(), map()) -> ok.
side_effects_in_order_dammit(F, M) ->
    Ordered = [{K, maps:get(K, M)} || K <- lists:sort(maps:keys(M))],
    ok = lists:foreach(F, Ordered).

But wait, what order should the keys be in, anyway?

This is a slow, steady march to insanity. “Give me iterators” begets “Let’s have ordered maps” begets “Let’s have ordered iterators for maps” and so on, and eventually you wind up with most of the Book of Genesis in the Devil’s Bible of Previously Decent Functional Languages. All the while, totally forgetting that these things already exist in another form. There are more data structures than just maps for a reason.

This just gets ridiculous, and it isn’t even what hashes are about to begin with.

Older Posts »

Powered by WordPress