> All I do is reason about the big things (sorting was mentioned).

It's hard to know what is big if the standard docs don't say. It's hard to know whether shifting (or popping) an element off a particular collection is big if the docs don't say.

If "shift"ing an arbitrary element off a Ruby Hash causes the entire hash table to get resized and rehashed, then shifting off all the elements one at a time is complexity O(nlogn) or O(n^2) (not sure off the top of my head). That puts what I tried to do a few days ago in the realm of "big things" like sorting. But I can't know ahead of time if the Hash#shift docs don't provide a clue.

When all I care about is the values in awk's associative array I just use the values as the keys.

So instead of
array = x
and then
for(i=1; i<=n; ++i) x = array...
I write
++array[x]
and then
for (x in array) ...

And yes - it can be a good strategy to start with the what your language and library provide and then rewrite as needed.

> Well, a hash is the most obvious choice for processing the
> mound of data in the way it needs processing. The built-in
> hash structures that comes with Ruby, Python, Java, etc.
> store not only the "values" but also the "keys" used to
> access the values. (That's why you can ask these built-in
> hashes for a list of keys, and they'll cough them right up
> for you.) But, wouldn't you know, I'm not interested in
> ever seeing the keys again in my beau's app.

If you can guarantee that your hashes are unique, then you can definitely implement a hash structure that doesn't keep references to the keys.

One thing that I've long considered a flaw in the Java Map class is that it puts far too much burden on the implementor. Often I just want an interface that has a single method: get(key) -> value.

It seems to me that this should be the base of a Map API and then there would be subclasses of this that would provide more functionality. That would make it possible to implement your structure as a standard map.

> > Each such layer will also add innecessary conversions
> > of data and data structures.
>
> Not necessarily. That's where generic programming shines:
> providing abstraction without penalty.

Yeah, you're right, generic programming in C++ (and also usage of non-virtual class system) allows this layer to be removed during compilation, so these abstractions give no penalty. But that's a special case in today's OO systems.

Probably it's just the whole static vs. dynamic thing. The more things you have static, you lose flexibility, but you can optimize much better.

> > There are ways out in my opinion. One is to take a look
> > at VHDL, for instance. It is a very modular language (for
> > hardware design), yet the final design is optimized as
> > a whole - there are no redundant data conversions after
> > the synthesis.
>
> It's comparatively easy to write such entirely declarative
> languages to address particular domains (DSLs), but I
> don't think anyone has really succeeded in making a
> general-purpose programming language that works that way.

The generic programming you mention is actually an example of paradigm that comes close to that in this respect.

> > Second approach is to decouple the data structures used
> > in the program from the actual program logic.
>
> Bingo. Tease out the abstract algorithm so you can reason
> about its efficiency.

Actually, I have an idea in mind based on that, below.

> > Any program
> > that uses a database essentially does that - the common
> > point is the database schema, and how exactly (with
> > what algorithms) it is implemented in the database is not
> > relevant. The actual database implementation can then
> > be optimized independently of the program, by choice of
> > indexes for example.
>
> Are you suggesting that programs that use databases don't
> have efficiency problems?

Well, they may have efficiency problems, but part of these problems can be easily solved by hinting the database (by normalizing the schema and creating the correct indexes). So you don't need to touch the program logic at all.

And that's my point. The program logic and the data structure implementation are somehow "decoupled" in programs that use databases (actually, it's still muddy if you use stored procedures, but that's another story).

Let me tell you more about my pet research project (which unfortunately, for the time being, competes with my other pet research projects).

I imagine a language where every data structure (especially the global ones, which cannot be described in terms of standard data structure) would be designed like a database scheme is usually designed. The actual implementation of the schemes would be thus completely decoupled from the program logic.

I even imagine that scheme implementation would be created by compiler (two manual passes - in first, compiler creates a test implementation, then you run tests of your program, you gather statistics about how the schemes are used, and in second pass, the compiler will use the gathered statistics as well as other user's input to create efficient implementation of the data structures).

I think this approach would have many advantages, most importantly, possibility to change the data structures used at will, depending on the change of requirements of program logic.

There are many interesting ideas in this direction. For example, compiler could implement the scheme in completely different way, and use the original scheme as a view of it, so the original scheme would be translated during compilation to the new scheme. You could even have older parts of program to reference the data structures in old way, while having newer parts to reference them in new way - like versioning of data structures.

Other idea is to have "virtual columns" in the scheme, which would be computed from values in other columns. The compiler would decide if it's worth to cache this value in the table, or if it should compute it at each use of this value (depending on how many inserts/reads you do and how difficult is to obtain the value).

So you see, there are bazillion possibilities, and also lot of interesting problems to overcome. However, it contradicts to current OOP paradigm (read: languages like Java, C#, Ruby, Groovy) in two fundamental ways:

1. Centralization of data structures - obviously, since I want to emphasize them. This contradicts having networks of small objects implementing the data structures.

2. The data structures are static for the run of program - if I want to optimize them, I need to know the type of usage ahead. This contradicts having dynamic language.

I generally find the idea of compiler that selects data structures for you depending on your actual needs and goals (speed, memory footprint) very intriguing, similar to the way that current compilers select instructions and registers for you instead of using assembler and doing it yourself.

> Well yes, of course I'm deliberately joking, so perhaps
> Chuck should have waited until April.
...
> And I'm rather liking your idea of an Extreme Programming
> Worst Practices article. If you submit it here we'd be
> happy to review it: http://www.artima.com/write.html

Thanks for the link! Hopefully I'll be inspired to write such an "article". :-)

> Well yes, of course I'm deliberately joking, so perhaps
> Chuck should have waited until April. But there is a
> serious point to my jokes, which is to get people to pay
> attention to performance.

I'll try to make the point that I think Morgan is making in a more constructive tone.

This article is a good one for developers don't know their asses from a holes in the ground. In my experience that's probably anywhere from 70 - 85% of developers. However, the portion of those developers that are reading Artima articles is pretty small. I think this article is inappropriate for the audience.

Probably every person reading this already knows to yield in a loop when you are polling. Everybody reading this knows that bubblesort is for boneheads. And finally everyone reading this knows it's impossible to write a Java program that doesn't crash or hang.

The silly loops with

goto

s make me suspect it was a joke.

I think all the algorithm stuff missed the point and just slips back into the nerdy safty zone of premature optimization. What I mean is that it seems like a lot slow code is not because of algorithm choice, but simply bad code.

The example of a slow app that you started out with was an installer. It may be that the installer is so slow because it is doing things like checking whether a file is already there, and if it is there, whether it has some reference count in the registry (assuming Windows) from a previous install, then comparing of the version of the already installed file to the version in the compressed archive. If it is doing all these things in such a way that it decompresses the file more than once, or accesses the file on disk many times (to get its size, then its last modified date, version, etc.) it performance will suck. Ironically, it can actually be a case where code that is well-decoupled and nicely object oriented performs worse than code that may be special-casing to gather all the registry information for all files in one shot, then all the information from the archive in another.

As far as the "blame the library" comments, I bet most of the time you shouldn't blame the library. Instread but you should blame your own code that is resorting the same array a thousand times.