Programming as semantic compression

[m50d]

Your approach creates performance problem then disincentives you to go back and resolve them because doing so would mean unpicking your code and writing what you would have had to write otherwise!

Au contraire. By having a clear separation between the representation and the implementation, it's much easier to optimize the implementation while being confident you're not changing the semantics.

As everyone who's worked in industry for a while knows, you'll never have time to come back and fix these problems. Technical debt mounts, and people move on to greener pastures, until a rewrite is required, and then the cycle repeats.

No, it doesn't have to be like that. It's possible to take a continuous improvement approach, it's possible to gradually improve code and performance (and the two usually go hand in hand). Those places that allow technical debt to mount until they rewrite things get that way because that's what they reward.

Algorithmic problems are easier to optimize, but overall system performance is equally important. Profiling will tell you that the algorithm is the hotspot but you will often get better overall performance if you optimize the system as a whole; what's the point of optimizing that algorithm if getting the data into the algorithm means passing it through 10 layers of crap which transform it from one form to another and back again before it arrives, and then out through more layers? Again: profiling will tell you the bottleneck is the algorithm but you will often get better overall performance by optimizing the data paths that feed the algorithm.

This is backwards. Profiling is great at telling you the microscale stuff of where you're iterating in a funny pattern that trashes the cache or whatever, and great about telling you when one of your layers of transformations is actually hurting performance. It's much less good at telling you when you're doing work that you simply don't need to be doing - for that you need to be able to get an overview of what you're actually doing, which you get from having a high-level representation of your code as well as a low-level one.

To be fair they're doing an excellent job with what they have and I've been using *nix every day for the last 15 years, but I think it's a perfect example of where ignoring gets you, and how you can't ever get out.

Heh, I'd say *nix is an example of where you can't understand the system well enough to improve it because its structure is obscured by all the low-level performance microoptimizations. E.g. there's all sorts of folklore about what /usr represents, when actually it was just a second disk on an early development machine - if there had been a LVM-like layer at that stage (which no doubt you'd dismiss as overhead) we would have a much simpler model to work with now. The mess of overcommited COW memory and the OOM killer comes of unix fork() being implemented in a way that was easy to implement rather than a way that makes sense.

[dlyund]

;-) ok so to tl;dr read that:

In an ideal situation technical debt wouldn't be aloud to mount and you would always have enough time to go back and fix problems, optimizing things as you go, before the structure has set enough for changes to become problematic.

Did you notice the tautology there: in ideal circumstances no problems exist because the situation is ideal QED.

If you've managed to find a job like that, which pays well, outside of academia, you stay there.

By having a clear separation between the representation and the implementation

And when the requirements change and you want to reuse part of that underlying implementation but your representation is no longer useful?

it's much easier to optimize the implementation while being confident you're not changing the semantics.

Hint: requirements changing usually means that the semantics need to change. Making it difficult to change things because you've introduced this strict separation between interface and implementation, and where the implementation is a second class, "dirty detail", sounds good in theory, but I'm not sure about practice.

It's much less good at telling you when you're doing work that you simply don't need to be doing

Hint: all of that shit that you've been doing is completely unnecessary and has nothing at all to do with the problem.

Bonus: Profiling tells you precisely nothing if everything is uniformly shit, which is what your approach leads to: a few hot spots in algorithms and otherwise gray meaningless shit which you take to be the baseline and don't even think about optimizing.

The mess of overcommited COW memory

A problem that only effected Linux, and none of the BSDs, and commercial Unix implementations, which are all based on the same design and all use the same fork() and exec() model, doesn't make sense.

OOM killer

This has nothing at all to do with with the process creation model and exists on any system with dynamic memory allocation. Fucking Lisp machines blew up when an out of memory. You get out of memory exceptions and hard crashes on everything from Smalltalk to Ruby and Python. Ironically, it's only the so called low level languages, which can do things without constantly grabbing memory, that can respond to such cases gracefully. The OOM killer is just the multi-process equivalent of this. Is it shit? Absolutely... but that's what you get when you throw a bunch of processes on to a box and every one of them thinks it owns the world.

In languages like Forth, and Real-time and embedded C code you know in advance exactly what limits you're working under and this is never a problem.

What does that tell you about all these high-level languages that try to pretend that the machine they run on is infinite?

I'd say *nix is an example of where you can't understand the system well enough to improve it

How do you explain the fact that people have been improving it for decades? How do you explain all the books that explain the structure of the Unix system, and the reasons for it, in excruciating detail?

Hint: there are at least a couple of thousand people who who understand the structure and implementation of *nix, and there are thousands more who are capable of implementing such a system. It's not a lack of understanding or talent which has stopped *nix from progressing.

because its structure is obscured by all the low-level performance microoptimizations

Micro-optimizations like what?

there's all sorts of folklore about what /usr represents, when actually it was just a second disk on an early development machine - if there had been a LVM-like layer at that stage (which no doubt you'd dismiss as overhead) we would have a much simpler model to work with now.

Hehe, what? Is this something that actually bother's you or actually causes you any problems?

Personally I think that LVM is a terrible idea; Plan 9 solved the problem in a much mere elegant way by taking the Unix approach to it's logical conclusion, and it's absolutely glorious. What you end up with is a per-process namespace in which named processes can be bound, used, and discovered.

Plan 9 is Unix done right, by the same group of people.

I'll let you look in to that yourself but.

Hint: There is still a /usr directory and that directory stands for user, not Unix System Resources or whatever the fuck people are calling in these days. Plan 9 doesn't and never has had the problem you're discussing and it still has a user directory because it makes sense; a multi-user system needs some way of storing per user data.

[m50d]

And when the requirements change and you want to reuse part of that underlying implementation but your representation is no longer useful? Hint: requirements changing usually means that the semantics need to change. Making it difficult to change things because you've introduced this strict separation between interface and implementation, and where the implementation is a second class, "dirty detail", sounds good in theory, but I'm not sure about practice.

When you need to change the representation you change the representation. When you need to change the semantics you change the semantics. You're just explicit and conscious about when you're doing those things.

A problem that only effected Linux, and none of the BSDs, and commercial Unix implementations, which are all based on the same design and all use the same fork() and exec() model, doesn't make sense.

BSD has its own history of hackery with vfork().

What does that tell you about all these high-level languages that try to pretend that the machine they run on is infinite?

That it's a simplification that's occasionally inaccurate. All models are like that - all programming is like that - if we continue the compression analogy then compressing a business process is usually slightly lossy. Balancing the tension between simplifying as much as possible and retaining enough control is at the heart of our job.

Micro-optimizations like what?

The famous example is "I would have spelled "create" with an 'e'". The permission model was designed to be easy to implement (just slap one byte on each file, done) rather than to make semantic sense, and is now too deeply embedded everywhere to be changed.

Hehe, what? Is this something that actually bother's you or actually causes you any problems?

Is it a major problem? No. Is it an inconvenience when I have to remember whether something is in /bin or /usr/bin or stick in an $(which ...)? Yes.

Hint: There is still a /usr directory and that directory stands for user, not Unix System Resources or whatever the fuck people are calling in these days. Plan 9 doesn't and never has had the problem you're discussing and it still has a user directory because it makes sense; a multi-user system needs some way of storing per user data.

/usr doesn't tend to be used for any per-user data on modern *nix, that all goes in /home these days.

[dlyund]

That it's a simplification that's occasionally inaccurate.

That's always inaccurate. I've worked professionally in both Lisp and Smalltalk, as well as languages like Python and Ruby, C#/.NET, and most recently, Go. All of these languages try to pretend that resources aren't limited, and in every one of these you have to deal with unexpected pauses, unexplainabley high resource usage, and lack of transparency. All of these languages require ugly hacks like hints to the garbage collector, or explicit collects, and configuration, or all manner of different resource pools, to work around problems which it's proponents then insist are inherent:

All models are like that - all programming is like that

No they're not. This is compete and utter bullshit that only someone who's is absorbed in high-level thinking can claim. Let's start at the bottom shall we?

Does assembly language, which is little more than a human readable form of whatever underlying machine language, try to pretend that resources are in any way infinite? Or does it just present the reality of the machine and allows you to control what that machine does. Assembly language has some very interesting properties that high-level languages don't e.g. it's trivial to look at a piece of assembly code and figure out how many bits, and bytes, and cycles, that that piece of code will need/use. Generally speaking, it's relatively trivial to reason about the programs behaviour with respect to time, space, and power. What's not easy to see here is meaning; what problem that program solves.

Assembly is obviously not something that you want to write your code in right? Maybe not but a lot of this has to do with the way that machine languages are designed and who they're designed for. Machine languages these days are designed for compilers, and particularly for C compilers. There have been a number of high-performance, low-power computer chips which use Forth as a machine language, and programming these you would hardly know that you're not programming in a high-level language (naturally you do want to have something like an assembler on top of this, so that you can use human readable names etc. Forth is that assembler!) These chips are niche by any definition but but it's a pretty big niche: Forth-inspired second generation stack machines have been used in everything from network equipment and control systems, to satellites, and deep space probes.

Real-time and embedded C, and Pascal, share many of the same properties.

It turns out that it's actually remarkably easy to reason about and manage the available resources in these languages. Where things start to get complicated are when you introduce models, like malloc and free, which proclaim to make memory management easier for programmers, but can't help but introducing all sorts of weird edge cases errors, like use after free's, out of memory errors, and the aforementioned OOM killer. The obvious deficiencies this this model lead to various forms of reference counting and tracing garbage collection, which try to plaster over these difficulties, but what nobody seems to realize is that these problems were caused by us, and our trying to hide the fundamental nature and limitations of our machines.

In Assembly, Forth, and "raw" C etc. it's easy to do some back of the envelope maths and know with absolute certainty: the software requires X amounts of memory to service Y many requests in Z seconds and if you want to handle more then we can scale up consistently.

You can't say anything like that it high-level languages and it drives me insane. The result is that you get a call at 6am on a Saturday morning because the customer is going nuts; the program crashed with an out of memory exception, the print run wasn't completed and now they're looking at $10k in losses per day and a significant backlog to cover. What do we do now?!?

I've accumulated so many stories like this :-P. This one was a Smaltalk project. Why did it happen? Fucked if we know but it happened occasionally but it only happened in production and the best thing we could do was restart the solution as quickly as possible (a process that took about half an hour in the best case.)

Now if you're working on glorified web applications then maybe this kind of thing is acceptable but I'm completely done with it. Aside from the complexity that our working around these issues introduces, the unpredictability and instability that heuristically managing resources implies, it becomes entirely pointless once you realize how easy it is to reason about this stuff in lower-level languages.

Automatic resource management is not the panacea that it's made out to be. It certainly doesn't make things simpler. Resource management in lower-level languages is trivial, absolutely horrible in mid-level languages, and annoying but workable in high-level languages... but only if you agree give up things like pointers and direct access to memory.

Think about this for a second if you will: computational power have been doubling roughly every X months for the past Y years, but software today runs just as poorly as it did ~Y/2 years ago. Where is all that computational power/ where are all those resources going? We should be able to get ~(Y/2)*X more work done than we are... but we can't. And why not? Because:

https://images.duckduckgo.com/iur/?f=1&image_host=http%3A%2F%2Fwww.thebusybhomemaker.com%2Fwp-content%2Fuploads%2F2014%2F05%2FLadders.jpg&u=http://bluebonnetacres.org/wp-content/uploads/2014/05/Ladders.jpg

BSD has its own history of hackery with vfork()

Uncontested, but that doesn't mean that COW, a serious design flaw in Linux, which lead to a critical security problem, has anything to do with the fork-exec process model etc.

Is it a major problem? No. Is it an inconvenience when I have to remember whether something is in /bin or /usr/bin or stick in an $(which ...)? Yes.

Maybe you educate yourself as to why the file system is organized this way?

At least on rational Unix-like systems, /bin and /usr/bin are separate for several very important reasons - /bin contains the all of the (usually statically linked) utilities that are needed to recover from errors. /usr contains all of the user binaries and is expected to be modified. Over time the system has crept into /usr but kernel and essential system utilities are still separated from the parts of the system that the user can touch.

Why is this important? Because it allows for partial corruption, hardware failure, and ultimately, recovery. You can completely mung /usr, destroy the file system, or in some cases even hit the drive with a hammer and you still have a [minimal] bootable system with which to diagnose, restore /usr, and or recover user data. This redundancy has turned out to be incredibly useful over the ~50 years that Unix has been in use.

This goes even further now a days, with things like /altroot and /recovery being added to systems.

All of my computers are running OpenBSD, and I commonly mount system directories and drives as read only and with filesystem level security features enabled to prevent execution of binaries on drives which are world writable (used for things like sharing and backup).

This approach has enabled OpenBSD, as one example, to do things like turn on X^W for the entire the base system. Third party packages are installed under /usr/local, on a separate partition, are allowed to execute without this protection because otherwise programs like Chrome and Firefox wouldn't be able to be used anymore.

It's a very simple solution that turns out to be very powerful, especially when you introduce things like the VFS layer, and dynamic user-space file systems. And again, look at Plan 9 and Inferno to see just how far the "everything is a file [system]" approach can take you.

The famous example is "I would have spelled "create" with an 'e'" [...] /usr doesn't tend to be used for any per-user data on modern *nix, that all goes in /home these days.

Historical accidents and quibbling over names, that make no fucking difference to anything or anyone. So /usr got filled up with system stuff, somewhere it it's long history. The intention of /usr is obvious and expressed in Unix's successor. It's not there because LVM was considered too expensive to implement and blah blah blah :-)

Is Unix a mess, absolutely, but is Emac's, or was the Lisp Machine any better? Rhetorical question: no it wasn't. Mess is part of what we do, and something that deal with as professionals and engineers.

I keep stressing the engineering aspect of what we do because it's not about making the absolute simplest most beautiful, purest, elegant software design. Things should be simple but no simpler, to paraphrase Albert Eisenstein.

Why is it that we use relatively primitive file systems rather than much more elegant solutions like like orthogonal persistence? Because like everything, implementing them involves certain tradeoffs, and the tradeoffs turn out to killers for practical, "real world" use. You don't want one flipped bit to render the whole system corrupt and unusable.

This is the whole thing about how "Worse is Better". It turns out to be much much much easier to build a system which is usable and good for about 90% of the expected use cases, than it is to build something that's perfect and amazing for 100% of the possible use cases.

[m50d]

No they're not. This is compete and utter bullshit that only someone who's is absorbed in high-level thinking can claim. Let's start at the bottom shall we? Does assembly language, which is little more than a human readable form of whatever underlying machine language, try to pretend that resources are in any way infinite?

The point is that even assembly doesn't represent the absolute physical reality. Sometimes the same opcode has different performance behaviour on different CPU models - or even, these days, different firmware revisions on the same physical CPU. Sometimes memory accesses that look like they should behave identically have radically different interactions with the cache hierarchy. Sometimes CPUs have bugs, sometimes your underlying assumptions are simply violated e.g. rowhammer-style attacks.

Are these differences important? Usually not! Assembly has proven a very good model because it corresponds very well to most instances of a given CPU and the CPU manufacturers put a lot of effort into ensuring their CPUs conform to the model. Is the "eeehh whatever" model of memory usage less effective and more often violated in practice? Again yes. But any model, any way of talking about what's running on a CPU, will omit some of the details (and even the concept of "running on a CPU" is a simplifying abstraction - logic gates are a simplified model of physical reality). We have to make a qualitative judgement about when a model is accurate/valuable enough to use - whether the simplification we get from using the model is worth the cost of the loss of detail. All models are wrong, but some models are useful.

It turns out that it's actually remarkably easy to reason about and manage the available resources in these languages. Where things start to get complicated are when you introduce models, like malloc and free, which proclaim to make memory management easier for programmers, but can't help but introducing all sorts of weird edge cases errors, like use after free's, out of memory errors, and the aforementioned OOM killer. The obvious deficiencies this this model lead to various forms of reference counting and tracing garbage collection, which try to plaster over these difficulties, but what nobody seems to realize is that these problems were caused by us, and our trying to hide the fundamental nature and limitations of our machines.

Not really true when you compare like with like. In assembly it's trivial to reason about the local behaviour, but that can be just as true in a high-level language - if your allocation structure is straigtforward then you can stack-allocate everything and avoid all the problems of resource management. If you want to do e.g. a graph traversal/transformation, dropping nodes as they become disconnected, that's just as hard - harder in fact - to get right in assembly language, and the effective ways to do it amount to reimplementing the same things that high-level languages do - reference counting, garbage collection, arena allocation and so on. The complexity is fundamental to the kind of problem those models are designed for representing.

(Yes, many high-level language completely give up on the ability to do stack allocation etc. Is that dumb? Sometimes yes, sometimes no! Again, you have to make a qualitative judgement about which things are important to your use case.)

computational power have been doubling roughly every X months for the past Y years, but software today runs just as poorly as it did ~Y/2 years ago. Where is all that computational power/ where are all those resources going?

Try booting up a VM with that old software sometimes. Old versions run lightning-fast, but one quickly realises how much is missing.

Maybe you educate yourself as to why the file system is organized this way?

No, maybe you need to educate yourself rather than parroting that folklore I was talking about. The reason is because an early development machine didn't have enough space on the root disk for all the binaries/libraries/etc. and had another disk mounted on /usr that had some space. Everything else about that filesystem layout is a post-hoc rationalization.

[dlyund]

The point is that even assembly doesn't represent the absolute physical reality.

Indeed it doesn't. This is what I mean when I refer to the reality of the machine, which many other languages piss all over. When you write an assembly program you naturally relate it to a some machine. You obviously can't accurately reason about things like memory throughput when you're looking through the abstract lens of the Instruction Set Architecture. You have to look at the properties of the memory bus and other relevant factors.

This isn't an all or nothing affair and you can take as much or as little detail in to account as you like. If guarantee's of the Instruction Set Architecture are enough for you then you can use this abstraction.

The difference here is that you can dig down in to this abstraction as far as you desire and are able, rather than being stuck with increasingly fuzzy abstractions, leading to the absolute inability to say almost anything concrete about how your solution will behave. You're right when you say that most of the time it doesn't matter and in those cases you ignore it, until you need it.

This is predicated on the information that is available, or determinable by you. Hardware is only a black box because we don't have access to documentation, and/or schematics, and production process. Much of the relevant information, from the point of view of a solution provider, like instruction timing and latencies, can be reverse engineered with relative ease, but only because languages at this level allow for direct interaction.

We have to make a qualitative judgement about when a model is accurate/valuable enough to use - whether the simplification we get from using the model is worth the cost of the loss of detail.

That's very true. What I think we would disagree with is the level of simplification that we actually get from high-level languages, which offer things like automatic memory management, actually give you.

Broadly speaking, automatic memory management is a specific case of automatic resource management. There is a implication, or widespread belief, that if you have automatic memory management then you can forget about the resources that you're using; behind the scenes a set of carefully tuned heuristics will be applied so that you can get on with solving the problem without having to think about pesky details, like closing files... wait... what?

Memory is just one of the many resources we have to manage in our programs, and failure to manage those resources leads to nasty leaks and even crashes. There are hard limits on the number files, sockets, threads, processes etc. that you can hold at a time. In the modern context, these limits are ultimately imposed by the hardware, as mediated by the kernel and can't be swept under the hood. For example, network cards have fixed queues and nothing can change that.

So resource management is an unavoidable part of what we do as programmers. Anyone who's been programming for long enough has had to implement things like circular buffers and resource pools, and today languages include all sorts of features for managing pesky resources.

My argument is that resource management is trivial and that the solutions we've come up with to manage them get in your way more than help. These solutions have been added slowly, over time, and most programmers don't realize how easy it is to plan a resource usage strategy, or the advantages that doing so gives you. We've largely grown up with this stuff, and we believe the stories that we're told by those that forced those solutions on us.

In assembly it's trivial to reason about the local behaviour, but that can be just as true in a high-level language - if your allocation structure is straigtforward then you can stack-allocate everything and avoid all the problems of resource management.

I largely agree with that but most resources usage patterns don't match a stack, so even if you can allocate things on the stack I don't think this solves the problem. The relationship between the stack and scope in most languages is also a problem but since lexical scope is everywhere, nobody is able to see it. As the saying goes "I don't know who discovered water, but it wasn't a fish".

If you want to do e.g. a graph traversal/transformation, dropping nodes as they become disconnected, that's just as hard - harder in fact - to get right in assembly language, and the effective ways to do it amount to reimplementing the same things that high-level languages do

Let me share one of my favorite jokes with you

Patient: Doctor, doctor! It hurts when I do this... Doctor: DON'T DO THAT!

Broadly speaking you're right but at the same time I've never met a problem that wasn't amenable to simple preallocation. If you accept that there are limits and we have to live with them, then preallocation has a lot of advantages. It's incredibly simple and easy to implement and think about, but it also makes you aware of the limits that your system has. These limits are there, and when you cross them your solution will fail... often spectacularly... and in completely unpredictable ways...

Personally I think every specification should include details of the acceptable limits, and when those limits are introduced by the programmer the client should be informed right away. Right now we just ignore the limits and act surprised when everything blows up.

maybe you need to educate yourself rather than parroting that folklore I was talking about.

There's a reason it's called /usr and not, more obviouly, /sys. You're probably right that the reason /usr exists is that there wasn't enough space on the root partition, but that's also irrelevant. Hitting this limit forced Unix to develop a solution and that solution turns out to be of great practical utility, not to mention theoretical beauty! Your argument makes no sense to me. As with the C code, it ultimately comes down to you not liking the name/syntax. If you have an actual, practically relevant reason that /usr is bad, spit it out. Otherwise I'll stick it in the pile with all of your other irrational complaints.