Cycles, memory, fuel and parking

December 31st, 2011

In high-performance, resource-constrained projects, you're not likely to suddenly run out of cycles – but you're quite likely to suddenly run out of memory. I think it's a bit similar to how it's easy to buy fuel for your car – but sometimes you just can't find a parking spot.

I think the difference comes from pricing. Processor cycles are priced similarly to fuel, whereas memory bytes are priced similarly to parking spots. I think I know the problem but not the solution – and will be glad to hear suggestions for a solution.

Cycles: gradual price adjustment

If you work on a processing-intensive project – rendering, simulation, machine learning – then, roughly, every time someone adds a feature, the program becomes a bit slower. Every slowdown makes the program a bit "worse" – marginally less useable and more annoying.

What this means is that every slowdown is frowned upon, and the slower the program becomes, the more a new slowdown is frowned upon. From "it got slower" to "it's annoyingly slow" to "we don't want to ship it this way" to "listen, we just can't ship it this way" – effectively, a developer slowing things down pays an increasingly high price. Not money, but a real price nonetheless – organizational pressure to optimize is proportionate to the amount of cycles spent.

Therefore, you can't "suddenly" run out of cycles - long before you really can't ship the program, there will be a growing pressure to optimize.

This is a bit similar to fuel prices – we can't "suddenly" run out of fuel. Rather, fuel prices will rise long before there'll actually be no fossil fuels left to dig out of the ground. (I'm not saying prices will rise "early enough to readjust", whatever "enough" means and whatever the options to "readjust" are –  just that prices will rise much earlier in absolute terms, at least 5-10 years earlier).

This also means that there can be no fuel shortages. When prices rise, less is purchased, but there's always (expensive) fuel waiting for those willing to pay the price. Similarly, when cycles become scarce, everyone spends more effort optimizing (pays a higher price), and some features become too costly to add (less is purchased) – but when you really need cycles, you can get them.

Memory: price jumps from zero to infinity

When there's enough memory, the cost of an allocated byte is zero. Nobody notices the memory footprint – roughly, RAM truly is RAM, the cost of memory access is the same no matter where objects are located and how much memory they occupy together. So who cares?

However, there comes a moment where the process won't fit into RAM anymore. If there's no swap space (embedded devices), the cost of allocated byte immediately jumps to infinity – the program won't run. Even if swapping is supported, once your working set doesn't fit into memory, things get very slow. So going past that limit is very costly – whereas getting near it costs nothing.

Since nobody cares about memory before you hit some arbitrary limit, this moment can be very sudden: without warning, suddenly you can't allocate anything.

This is a bit similar to a parking lot, where the first vehicle is as cheap to park as the next and the last – and then you can't park at all. Actually, it's even worse - memory is more similar to an unmarked parking lot, where people park any way they like, leaving much unused space. Then when a new car arrives, it can't be parked unless every other car is moved – but the drivers are not there.

(Actually, an unmarked parking lot is analogous to fragmented memory, and it's solved by heap compaction by introducing a runtime latency. But the biggest problem with real memory is that people allocate many big chunks where few small ones could be used, and probably would be used if memory cost was something above zero. Can you think of a real-world analogy for that?..)

Why not price memory the way we price cycles?

I'd very much like to find a way to price memory – both instructions and data - the way we naturally price cycles. It'd be nice to have organizational pressure mount proportionately to the amount of memory spent.

But I just don't quite see how to do it, except in environments where it happens naturally. For instance, on a server farm, larger memory footprint can mean that you need more servers – pressure naturally mounts to reduce the footprint. Not so on a dedicated PC or an embedded device.

Why isn't parking like fuel, for that matter? Why are there so many places where you'd expect to find huge underground parking lots – everybody wants to park there – but instead find parking shortages? Why doesn't the price of parking spots rise as spots become taken, at least where I live?

Well, basically, fuel is not parking – you can transport fuel but not parking spots, for example, so it's a different kind of competition – and then we treat them differently for whatever social reason. I'm not going to dwell on fuel vs parking – it's my analogy, not my subject. But, just as an example, it's perfectly possible to establish fuel price controls and get fuel shortages, and then fuel becomes like parking, in a bad way. Likewise, you could implement dynamic pricing of parking spots – more easily with today's technology than, say, 50 years ago.

Back to cycles vs memory – you could, in theory, "start worrying" long before you're out of memory, seeing that memory consumption increases. It's just not how worrying works, though. If you have 1G of memory, everybody knows that you can ship the program when it consumes 950M as easily as when it consumes 250M. Developers just shrug and move along. With speed, you genuinely start worrying when it starts dropping, because both you and the users notice the drop – even if the program is "still usable".

It's pretty hard to create "artificial worries". Maybe it's a cultural thing – maybe some organizations more easily believe in goals set by management than others. If a manager says, "reduce memory consumption", do you say "Yes, sir!" – or do you say, "Are you serious? We have 100M available – but features X, Y and Z are not implemented and users want them!"

Do you seriously fight to achieve nominal goals, or do you only care about the ultimate goals of the project? Does management reward you for achieving nominal goals, or does it ultimately only care about real goals?

If the organization believes in nominal goals, then it can actually start optimizing memory consumption long before it runs out of memory – but sincerely believing in nominal goals is dangerous. There's something very healthy in a culture skeptical about anything that sounds good but clearly isn't the most important and urgent thing to do. Without that skepticism, it's easy to get off track.

How would you go about creating a "memory-consumption-aware culture"? I can think of nothing except paying per byte saved - but, while it sounds like a good direction with parking spots, with developers it could become quite a perverse incentive...

1. gwerDec 31, 2011

But to some extent, we already pay for memory use in cycles – the more memory you use, the more you tend to blow the caches (L1, L2, etc.) and damage your performance by large constants. When you start swapping out, that's just you blowing another cache.

2. Z.T.Dec 31, 2011

If you believe that shaming developers about security bugs found in their code helps them avoid making more security bugs, maybe have a "reduce memory consumption day" like a "bug hunt day" and shame developers in whose modules memory consumption was reduced the most (without impacting performance, maintainability, etc.)

3. Darius BaconDec 31, 2011

I don't know, but I'm reminded that in this paper's algorithms to auction both time and space, doing it for time is a *lot* simpler:

(I say I don't know because our day-to-day problems are pretty far from the paper's setup.)

4. Stefan DragnevDec 31, 2011

I could extend the metaphor here. Public transportation is like cloud services – you pay small for the small time you use the service. You don't pay for infrastructure (the car itself), only for what you use from it. You also can't really get the comfort of a personal transportation vehicle.

5. Yossi KreininDec 31, 2011

@gwer: it's true that we pay for memory use that way, but it's very erratic – you can preallocate a huge pool of objects and it doesn't affect your cache performance at all; I could go on, but the idea is, the price can depend on the memory footprint but it's far from a simple and/or continuous function.

@Z.T.: I guess I don't like to think of it as "shame", but it probably does work with security bugs because everybody knows their security bug is a very real problem they created. With memory, developers can reasonably think to themselves, "c'mon, I didn't care about memory consumption – nor should I!" – because memory consumption is not a real problem, at least until the moment when it is.

@Darius: interesting – I should read it.

@Stefan: I guess you could say that – especially where "public transportation" is actually a private service... If it's subsidized or the price is otherwise distorted, as it usually is, and if the decision which routes are available is made by some municipal body, then you start getting other kinds of special effects.

6. RichardJan 1, 2012

mmap()'d caches like Varnish implements might be one possible answer – as unused memory becomes more scarce, their performance drops because the probability of the object you want to retrieve being already paged in drops.

Any kind of cache that can lazily, dynamically adjust to the amount of memory left free ought to exhibit a similar gradually-changing performance characteristic.

7. ConfusedJan 1, 2012

Amazon S3 sure knows how to price memory...

Are you suggesting a memory aware programming culture which dynamically chooses the most effective algorithm to use for a task? For instance, a search task which dynamically chooses an algorithm using an O(1) hash lookup that optimizes Cycles vs. a O(log(n)) binary search that optimizes memory? The lookup would be preferred assuming the hash table can fit in memory.

One way to change the culture would be to make the developer + architect do 50 pushups for every byte they allocate on the heap.

8. alexJan 1, 2012

"If a manager says, “reduce memory consumption”, do you say “Yes, sir!” – or do you say, “Are you serious? We have 100M available – but features X, Y and Z are not implemented and users want them!”"

As a programmer, I would say, "OMG, thank you!". It's managers who always push for more features, because they see pressure from users. Programmers want the time to clean things up, because it's where we work.

9. Yossi KreininJan 1, 2012

@alex: it's not that the manager says "reduce memory consumption, here's a timeout from other work" – just "reduce memory consumption" :) Another angle is that reducing memory consumption is not necessarily a clean-up, much like reducing runtime isn't – efficient code is frequently uglier. In this sense, pushing for efficiency is pushing for "features" both because it's a "feature" as far as a customer is concerned and because it "pushes for ugliness" as much as or more than any other feature bolted on under pressure.

10. BryceJan 2, 2012

Feature push and bad features are maybe the real problem here. I get surprised how much software goes from good to bloated and overcomplex because any old feature users ask for gets shoveled in without regard to the overall effect on usability.

Now if you need to reduce memory use for the same feature set then I guess you really need to come up with some draconian coding guidelines to avoid language features that lead to bloated code size, make all your own data structures, your own memory manager, etc., probably your own compiler is not a bad idea.

11. Johan OuwerkerkJan 2, 2012

For a high throughput kind of program that's true, however for I/O bound tasks where latency is important this no longer works. A reduction in memory footprint directly translates into an ability to run more instances of a task in parallel, which is usually more valuable as raw performance is capped by I/O bandwidth anyway.

You can also see this in folding@home type projects (the less memory each task needs, the more you can cram on that card) and in realtime 3d graphics — especially consumer oriented versions of that (where you might well have to contend with tons of services/apps on an overly optimistic choice of hardware for the OS).

12. Gareth ReesJan 4, 2016

When I worked on console videogames, running out of memory was a vital concern (as you point out, when there's no swap, the price of memory suddenly goes to infinity). The way that we dealt with this was to maintain a memory budget for each project. Like a corporation deciding how much money it's going to spend on manufacturing, R&D, marketing, sales, back office, etc., we would assign memory by function. Code, stack, level data, sound effects, streaming music, 3d models, textures, and dynamic (garbage-collected) heap would each get their own budget. The budget was enforced by the memory management module, so that the pain of exceeding the budget was felt immediately by the department that was responsible for it. If you added another dozen photo-realistic textures, the game would refuse to load the level, and it would up to you to figure out how to compress or tile or share the textures, or simply do without. Of course, the requirements of the game might need the budgets to be revised, but this was a heavyweight process, and of course the department who budget was being proposed to be cut would push back, so it was nearly always easier to find a way to live within your means.

13. Yossi KreininJan 5, 2016

Good stuff. You need to be able to come up with a good budget and to maintain/change it over time for this to work, of course; some organizations are better at it than others. What I like about how processor cycles work is, if you have no budget, just a status quo, there's a pressure mounting gradually as things get worse, even if the org isn't great at managing a budget... Anyway, it's inspiring to hear that there exist places where the budget approach works well.

14. Bruce DawsonJan 6, 2016

Have you read "The High Cost of Free Parking"? It seems relevant. The author rails against zoning that requires developers to supply huge amounts of free parking.

They also recommend that metered parking should be priced such that occupancy typically peaks at about 85%. Perhaps that can be mapped, somehow, to memory optimization on computers?

I don't think they consider the possibility of adjusting the parking price in real-time based on occupancy – the unpredictability of that method would be problematic.

15. Yossi KreininJan 6, 2016

Where I live they have laws taxing developers on too much underground parking in buildings... (Or so they say, I never checked the facts and heard at least one person claim it's an urban legend.)

85% sounds interesting, the question is what pricing mechanism to use.

Post a comment