We already have a purely functional linux distro that is immutable and stateless, called NixOS
An immutable operating system
111–120 of 153 posts
Re: An immutable operating system
#112Earlier quoted context omitted.
> For an operating system latency is more important than through put One interesting exception to this rule is operating systems for network packet routers. These need to be optimized for throughput over latency. I mean, the difference between 10 and 20 million packets per second is important, but the difference between 10 and 20 microseconds of processing delay is not. This is a fun area to be in at the moment becau…
When you're talking about an average latency of single digit us for a regular switch and < 500ns for a low-end performance switch, the difference between 10 and 20 microseconds is massive.
Accidentally clicked on the wrong icon and downvoted you, sorry, my bad.
Re: An immutable operating system
#113'Clojure has transients, which basically means "inside this function, use a mutable value under the hood while building up the value, but make it immutable before it's returned"' is this essentially a ... closure?
Re: An immutable operating system
#114I wrote an operating system in a purely functional dialect of Lisp; http://losak.sf.net There are a few things I learned in the process that I think are relevant here: 1. Forget garbage collection in the sense of any variant of mark-and-sweep. For an operating system latency is more important than through put, so you really want real time memory management. If you use reference counting, then there is a lazy variant…
Author here. The language is the part I also dread the most, and is also the part that will be the least unique and the least interesting to "re-invent".. I'll look into finding an existing language that runs on bare metal and that has (or supports) immutable values.
There were some dataflow languages like VAL or SISAL that did exactly that. The hardware and software on top was built in the 70s and 80s, but such parallel research funding sort of dried out after the cold war ended.
There is a resurgence of dataflow related research again, which you would probably be interested in. For example, Jack Dennis is pushing the 'Fresh Breeze Architecture': a write-only-once memory CPU with in-hardware GC. This should be right up your alley:
Re: An immutable operating system
#115Earlier quoted context omitted.
Generational GC usually depends on write barriers to detect creation of references to newer generations inside older generations. Immutability prevents the mutation of older generations, so no new references can occur. So I expect generational GC to be easier to implement. I wouldn't expect it to be faster or slower though, because programs will need to be written differently to cope with the limitations on mutabilit…
In the case of Clojure, log is log base 32, so it's close enough to O(1) as to make no difference in most circumstances.
Many immutable algorithms replace arrays with trees. Trees are pointer-heavy, and pointers are less cache-friendly than arrays.
Memory access is often over 100x the cost of an L1 cache hit. It doesn't take too many of those to make a big difference if you're CPU bound.
My comments are general, I'm sure Clojure has access to arrays where necessary for interop at least.
Re: An immutable operating system
#116Earlier quoted context omitted.
Tracing garbage collection has better throughput than reference counting, but reference counting has lower and more predictable latency. If you were actually going to try do tracing GC on the operating system level, you would probably have to use one of the more involved GC algorithms that require kernel support like Azul's C4 collector.
> you would probably have to use one of the more involved GC algorithms that require kernel support like Azul's C4 collector Which shouldn't be such a problem if you're already writing an OS? Also AIUI the only "hard part" of C4 is making sure objects don't get modified while they're being moved (that's what the barrier's there to detect) - which isn't a problem if everything's immutable.
> Which shouldn't be such a problem if you're already writing an OS?
I guess that could've used more context. I was trying to point out that in the larger landscape of GC algorithms, the one used by .NET is not that advanced, even though it's better than the GC used by common scripting languages.
> Also AIUI the only "hard part" of C4 is making sure objects don't get modified while they're being moved (that's what the barrier's there to detect) - which isn't a problem if everything's immutable.
Would absolutely everything be immutable? How would you implement lazy evaluation with the correct time complexity?
The expensive part of any garbage collector with short pause times is bound to be the read barrier, which is still needed with only immutable data. If the GC is compacting and wants to relocate an object, it has to rewrite all references to point to the new copy of the object.
C4 uses a read barrier to enforce the invariant that all references point to the up-to-date copy on a load of a reference, not just on a use of a reference. It relies on its ability to immediately update all references to reuse compacted pages during compaction, which means that gratuitous amounts of free memory are not required (a common problem with moving collectors).
You might be able to come up with alternate collector design that uses some of the same ideas as C4 while exploiting immutability, but if you loosen the healing read barrier you weaken your ability to reuse memory and put a bound on memory growth, since a reference to an old copy might always escape to the next round of collection.
Re: An immutable operating system
#117I wrote an operating system in a purely functional dialect of Lisp; http://losak.sf.net There are a few things I learned in the process that I think are relevant here: 1. Forget garbage collection in the sense of any variant of mark-and-sweep. For an operating system latency is more important than through put, so you really want real time memory management. If you use reference counting, then there is a lazy variant…
Forget garbage collection in the sense of any variant of mark-and-sweep. For an operating system latency is more important than through put, so you really want real time memory management. Is the assumption that mark and sweep is slower than real-time memory management? It's actually been proven false, e.g. the .NET CLR runs faster than native C code in certain situations. If you use reference counting, then there is…
> It's actually been proven false, e.g. the .NET CLR runs faster than native C code in certain situations.
[citation needed]
and by citation I mean example code that "proves" this.
Re: An immutable operating system
#118Earlier quoted context omitted.
Author here. The language is the part I also dread the most, and is also the part that will be the least unique and the least interesting to "re-invent".. I'll look into finding an existing language that runs on bare metal and that has (or supports) immutable values.
Haskell
- HaLVM : https://github.com/GaloisInc/HaLVM
- House: http://programatica.cs.pdx.edu/House/
- SeL4 : http://ssrg.nicta.com.au/projects/seL4/
Emphasis is on the security and verifiability typed, pure-by-default Haskell provides, over OS design.
Re: An immutable operating system
#119This idea reminds me of what Go is doing with their channels to solve concurrency issues: they're essentially sharing data by copying the data. Copying data is slow and that's why Go's channels aren't the fastest solution, but they're less complex than dealing with the traditional concurrency issues. I've written a toy kernel and I just can't imagine copying all process data because 1 little thing changed. However, t…
When you fork() a process you don't have to copy all process data either, thanks to copy-on-write semantics.
Re: An immutable operating system
#120Awesome! You should have a look at Urbit: http://www.urbit.org/
There appears to be no "About" on that site. Who knows what on earth it is?
On the left sidebar, the "documentation" link is to a video. No thanks, I'm look for a sentence of text.
The next link down is a 404 error.
The community link is for insiders...lots of comments about people leaving the building,whatever that means.
Bottom of page, how to install. Why am I installing something when I don't know what it is?
Sites that expect you to already know what they are about, and do not deign to give so much as a sentence of explanation, are extraordinarily frustrating.