Hacker News Reader

Comment by whack | Hacker News Reader

Rule 6: Every well-intentioned rule will be bastardized and used to justify horrible code.

Foo: "Hey, this 10000-element collection, which we do repeated lookups on... why are we using a list and not a HashSet?"

Bar: "Because lists are so much simpler than a HashSet. Let's just KISS"

Foo: "But... doing repeated lookups on a 10k sized list is so much slower than just using a HashSet!"

Bar: "Oh really? Have you profiled the entire application, and measured the latency impact caused by this decision? Come back to me once you've done so, and until then, we're not going to tune for speed."

View on HN

One framework that helps me a lot with these discussions is to treat a lot of rules and advice as directional rather than absolute. For instance, if you have an intern who gets stuck and spends a whole week trying to figure out something that a teammate would be able to work out with him in 30 minutes, you might say, "ask for advice when you get stuck". But if you have a different intern who bothers you all the time instead of trying to figure out anything on their own, you might say, "try and figure things out for yourself". These are contradictory pieces of advice, but they're meant for different people so they're not truly contradictory.

Pike's rules are very good directionally for a certain clever and diligent type of programmer who knows their CS fundamentals but sometimes overthinks what they're doing. If you are Rob Pike and you work places like Bell Labs or Google, you are going to be surrounded by more of these people and your advice is going to be directionally aimed at them. If you work with people who are sloppy or have poor CS fundamentals, you're going to want to give them different advice than Rob Pike gives his coworkers.

(In your example, people don't usually get as militantly stupid as Bar unless Foo is somehow antagonizing them or being too argumentative with his advice, which is a completely different aspect of giving advice. Either that, or Bar is a particular combination of "smart enough to rationalize their original position" and "stubborn enough not to give up their original position".)

Ironically, in that situation, using a list might end up being more efficient due to cache locality. Or not. That's why measuring is so important, since performance can be a very counterintuitive subject. Hard-data should always prevail over theory and guesswork.

If it's that bad, it should be easy to discover what is fastest.

But the way too common situation is that you look at a program under development and tell people "no way, that list will be too large to keep searching, you should design it around a hash set", and people reply something about premature optimization and keep going, then it gets released and is too slow to use so you get to rewrite all their code under pressure.

"Lists", presumably referencing a linked list, have horrible cache locality. You were thinking of an array?

The rise of Python and similar languages have muddied the distinction between "lists" and "arrays".

For any realistic workload containing a mix of failed-lookups, and lookup-hits midway through the list, we're talking about many thousands of comparisons for a single lookup on average. Regardless, replace list with linked-list in the above example, for illustrative purposes.

I agree that measurements & hard-data are preferable to guesswork, but it takes time and energy to gather these measurements and hard-data as well. For minor decisions where the alternative proposal is very slightly more complex, but there's a very compelling reason to assume order-of-magnitude performance improvements, I would argue that gathering data is a waste of time.

Isn't a degenerate hash set a linked list?

If it uses open hashing, yes. A degenerate closed-hashing hash set becomes an array.

Bad practitioners in any field crudely invoke and naively apply a trite toolbox of mantras. Detached from reality and driven by insecure ego, they become the problem by using magical thinking from authoritarian logic and delude themselves of the reality of what they are actually doing.

In any skill, people can fall prey to cults of myth and mysticism as they merit based on adherence to orthodoxy rather than suitability. Programming is no different and sometimes it's hard to hear anybody think over the mooing of all the sacred cows.

Vector or array? Sure. List is worst of both worlds

If they don't need order, a hash set is indeed more simple conceptually.

A set, the abstract interface, is simpler conceptually than a list. A hash set, the particular implementation of a set, is more complex.

Fortunately there are many languages which will provide a generic abstraction for you, so you don't have to deal with any of the complexity of implementing a hash set and you can just treat it like a set.

Lots of code is written in C :)

Or Go.

In Go, it's idiomatic to use map[T]struct{} for a HashSet. In fact, the compiler optimises struct{} so that it doesn't even allocate.

This is also how HashSet is implemented in Rust (internally its a HashMap<T, ()>, and zero sized structs are optimized out just like Go).

But by providing a set type, Rust is able to provide for users various set operations which Go requires you to write by hand. It becomes hard to argue that a set is simpler than a slice when you have to write your own methods dealing with union, disjunction, intersection, difference, subsets/supersets, etc every time.

One could easily implement a hash set with an array, the reverse is not true at all. From the outside, arrays are extremely flexible, powerful, and complex constructs; a set, even a hash set, is not.

If it is easy to procure a set (as a hash set), then sets should be used when they could be used instead of arrays (unless there are performance concerns to using sets). In languages that do not include batteries (e.g. C), it makes sense to use an array simply because procuring a set isn't easy.

I'm probably missing something, but eg awk implements its 'arrays' at least logically with something like a hash set, and indeed hash sets can be great for (say) sparse arrays.

Lots of low-level data structures can be implemented in terms of one another, and which makes sense depends on circumstance.

Low level doesn't mean simple. In this case, arrays provide a lot of flexibility with manual indexing. They are a low level hammer that can do anything.

Sets are much more restricted, they don't have manual indexing, they don't garaunteed iteration ordering without special semantics, they don't do as much as arrays even if they might be implemented with arrays.

Then why use an array when you only need a set and an array would be overkill?

YAGNI and KISS are the two most frequent targets of Rule 6.

Rule 6 is a corollary of "Every principle, and every group or movement based on a principle, eventually becomes its own opposite."

Rule 6.1: Rule 6 is excluded from Rule 6.

Incidentally, Plan 9 was just 6 upside down.

Or just abstract over both of them? For some cases that would make transitioning between the two, and profiling them, very easy.

How is writing code that loops over a list simpler than calling:

things.Get("key")

Your "Get" method hides complexity. It could be that it loops over a list, or that it hashes to find the bin, then loops over the list of items in the bin, or any of other dozens of other possible implementations.

So the next question is "What's the implementation of the Get(key) method?" Or maybe "Why aren't you using your language's library methods to loop over that list?"

Why are you even asking the question if profiling hasn't determined a performance problem in that bit of code?

I'm considering cases where looping over a list mean using a simpler algorithm than whatever's provided by "Get", applying rules #3+#4, after determining that "Get" is a bottleneck.

Is this really an explanation of why manually iterating over a list is simpler than just calling a method?

Get is simpler precisely because it hides the complexity.

> Or maybe "Why aren't you using your language's library methods to loop over that list?"

What makes those methods not subject to the "hiding complexity" objection?

It's an ill-considered stream of consciousness where I wasn't clearly separating "simplicity of interface" from "simplicity of implementation".

Part of what I was going for is that a clean interface might hide a complex implementation. If you've followed rule 1 and see that "Get" is a bottleneck, it makes sense to apply rules 3+4, and see if there isn't a simpler implementation than the one provided by "Get".

The interface is the same. For example, in C# you have an interface Collection, which offers a lookup method, and which both HashSet and Lists implement.

The point of the OP is that among different implementations for the same interface, choose the simplest one unless you have empirical evidence that compels you to do otherwise.

Arrays didn't implement interfaces in C# until the Linq release. But the main problem is that arrays have an interface st is much more complex than just ICollection, they have functionality you don't want to be used and that should be properly encapsulated.

> which offers a lookup method, and which both HashSet and Lists implement

How does a List map values to key? How does it even represent them?

The lookup method just checks whether an element exists in a collection or not. List and HashSet implement non-indexable collections, which have no notion of key. The Collection interface is very thin, and it's mostly used when you need to keep track of a set of elements. E.g. storing the nodes already visited in a dfs.

OK I know more about C# now than I ever planned on knowing.

The problem with OP comment is that KISS and premature optimization are not diametrically opposed. Thet are two separate principles that mean different things.

Premature optimization is bad, but not because it necessarily violates KISS. Similarly, many people overcomplicate code for reasons nothing to do with optimization.

His argument reminds me of people who argue against free speech generally because we already ban people shouting fire in a cinema.

As tuples? You can very easily traverse the list, check for the key in the 0 index of the tuple, and get the value on the 1 index.

Not efficient, but very much possible.

In terms of programmer time/effort, using .Get() is simpler.

In terms of program speed/optimization, the answer depends on how .Get() is implemented.

Writing simple programs that meets requirements should be your goal.

Premature optimization is the root of all evil.

Simplicity is great when it's not borne of ignorance and when it doesn't over-simplify. Some things are unavoidably complex. Even the word "simple" is complex, and has many meanings. What if simple is defined as...

- relies on simple "Programming 101" concepts

- doesn't require using or learning a framework or library

- corollary to above, doesn't require ascertaining that said framework or library implements a .Get() method

- doesn't rely on anyone else's code and has no dependencies or references

- doesn't require understanding ancillary concepts that might be present such as hash tables

Then writing the loop is "simpler." To answer your original question.

And just to turn things completely topsy-turvy, how about your .Get() method. If it's implemented the way such things are usually implemented, that means it uses hash tables and is very efficient. But that means it's a premature optimization, right, and therefore the devil? (Well we haven't defined "premature" either.)

The real answer is to think for yourself like a grown-up and don't rely on dogma. Every situation is different; tackle every problem by optimizing for what's important in that specific problem, using whatever resources and minding whatever constraints apply to that specific problem.

Selecting appropriate data structures and algorithms for a problem is not optimization. It's one of the basic skills and responsibilities of a programmer. That's why the bulk of the first volume of Knuth's _The Art of Computer Programming_ is about data structures.

Using the Set interface is probably the right thing. Then you profile, and if the set implementation you chose is too slow, you just swap it out for another implementation that implements the Set interface.

Who said you get to use a ready-made Get method / hash?

Sorry, but Bar is right. Unless you have profiled, the list is fine.

It might even be faster (cache locality etc as another said -- if the list is contiguous).

But even more so: you don't even need to profile, unless you have an actual problem with execution speed. If it's fast enough that you don't have to care, you don't have to care.

Reply on news.ycombinator.com