OSDev.org

Brendan wrote:In the most general possible terms, I'd question whether very fine grained isolation (e.g. "per object") is worth the extra/unavoidable overhead (regardless of how it's done - with segmentation, managed code or something else); and whether coarse grained isolation (e.g. isolating processes from each other) is a much better compromise between granularity and overhead.

Rusky wrote:

Brendan wrote:In the most general possible terms, I'd question whether very fine grained isolation (e.g. "per object") is worth the extra/unavoidable overhead (regardless of how it's done - with segmentation, managed code or something else); and whether coarse grained isolation (e.g. isolating processes from each other) is a much better compromise between granularity and overhead.

In situations where managed code (in the sense of compiler-verified memory access, not wrt GC, et. al.) is acceptable, it's actually a pretty easy decision. When your compiler can verify, with no runtime overhead, that all memory accesses are in bounds, why would you not use that method?

• The code being compiled is so simple that it doesn't matter what you do, or
• The language used is so restrictive that it's virtually useless for anything of reasonable complexity, or
• The performance of the resulting code is so bad that you wish you could've used a language that does run-time checks instead, or
• You've broken the world record for the most complex (and most error prone) compiler in history

Rusky wrote:Of course, there are still runtime checks of some variables, but only the ones that are necessary and only when they're not redundant.

Rusky wrote:Might be good to learn some computing theory.

It's not overhead if it's actually impossible to get by, securely, without it. The checks that are necessary are for things outside of what the compiler can possibly know in this universe, such as reading random bytes from the network. The compiler verifies, without requiring unnecessary or redundant runtime checks, that all memory access is in bounds, not only some.

Rusky wrote:Yes, that's all, 100%, every memory access. All of them. They are all verified to be in range at compile time. This is partly accomplished by disallowing them in certain branches where addresses are not guaranteed to be in bounds. Yes, that means there will be runtime checks, but there will not be extra, redundant, overhead-causing ones.

Brendan wrote:Think of it in terms of certainty. If the code says "let i = 3" then the compiler can be reasonably certain that "i == 3". If the documentation for a kernel API function says "This function will only ever return values from 0 to 3", then the programmer can be reasonably certain that the kernel API function will only ever return the values from 0 to 3, but the compiler can't/won't know that. For IO, depending on where the data comes from (e.g. reading from an "untrusted" file vs. IPC from another instance of the same executable) the programmer may be certain about the values the data contains, but the compiler can't/won't know.

Brendan wrote:Then there's things that in theory the compiler could know, but in practice the compiler doesn't know because it's too complicated to figure out (e.g. no sane programmer will ever expect any compiler to generate 100% optimal code in every possible case, including removing unnecessary checks - 100% optimal code is like absolute zero in that it exists but isn't achievable in practice).

Rusky wrote:

Brendan wrote:Then there's things that in theory the compiler could know, but in practice the compiler doesn't know because it's too complicated to figure out (e.g. no sane programmer will ever expect any compiler to generate 100% optimal code in every possible case, including removing unnecessary checks - 100% optimal code is like absolute zero in that it exists but isn't achievable in practice).

What are some examples of this, in the case of bounds checking? I've given some pretty strong support for dependent types' abilities, you've just asserted that some things are "too complicated" for the compiler.

int myArray[1234];

int foo(int index) {
    return myArray[index];
}

Rusky wrote:When compiling this code:

Code: Select all

int myArray[1234];

int foo(int index) {
    return myArray[index];
}

The compiler reports an error that index can be out of range. To fix it, you either specify in the type of foo that index must be in [0,1234), or you add a check for whether it's in range. No knowledge of other files necessary.

int myArray[10];

int foo(int value) {
    return myArray[value & 15];
}

Rusky wrote:I'm beginning to think you didn't so much as glance at any of those papers or even google dependent types...

Brendan wrote:Are you going to write a compiler that has a special integer type for numbers "from 0 to 9, or from 16 to 25, or from 32 to 41, or ...."?

Do I need to get more complex (maybe "return myArray[ sqrt(value) & 251];")?

Brendan wrote:I did glance at the second one briefly. To be perfectly honest, I saw "ML" and put it in the "wanky academic crap" pile..

Rusky wrote:

Brendan wrote:Are you going to write a compiler that has a special integer type for numbers "from 0 to 9, or from 16 to 25, or from 32 to 41, or ...."?

Do I need to get more complex (maybe "return myArray[ sqrt(value) & 251];")?

How about a compiler with general types for integers that satisfy certain conditions? sqrt is trivial to deal with in that way; bitwise operators are a little trickier but still possible AFAIK. (If not, how useful is indexing an array with the result of a bitwise and anyway?)

Rusky wrote:

Brendan wrote:I did glance at the second one briefly. To be perfectly honest, I saw "ML" and put it in the "wanky academic crap" pile..

If you could get over your pretensions, you would probably sound a bit less silly.

Brendan wrote:Hash tables (if modulo is overkill)?

Brendan wrote:"Rain increases the chance of car accidents. To improve safety, I invented a "functional car" - as soon as it detects the smallest drop of water it jams on the breaks, turns of the engine and refuses to move. People laugh at my "functional car" and call it funny names (like "non-functioning car"). I've been pushing the idea for over 50 years and still can't understand why nobody wants it."

"State increases the chance of programming mistakes. To improve "correctness", I invented "functional programming" - as soon as it detects the smallest amount of state, it spits out an error message and refuses to compile. People laugh at my "functional programming" and call it funny names (like "non-functioning programming"). I've been pushing the idea for over 50 years and still can't understand why nobody wants it."

Rusky wrote:

Brendan wrote:Hash tables (if modulo is overkill)?

Modulo is significantly closer to what you mean (not to mention significantly simpler to handle with dependent types), and any optimizing compiler from the past few decades ought to be able to perform strength reduction on it.

Rusky wrote:

Brendan wrote:"Rain increases the chance of car accidents. To improve safety, I invented a "functional car" - as soon as it detects the smallest drop of water it jams on the breaks, turns of the engine and refuses to move. People laugh at my "functional car" and call it funny names (like "non-functioning car"). I've been pushing the idea for over 50 years and still can't understand why nobody wants it."

"State increases the chance of programming mistakes. To improve "correctness", I invented "functional programming" - as soon as it detects the smallest amount of state, it spits out an error message and refuses to compile. People laugh at my "functional programming" and call it funny names (like "non-functioning programming"). I've been pushing the idea for over 50 years and still can't understand why nobody wants it."

... and there you go again. ML does, in fact, allow mutable state. In addition, one of the papers I linked to applies dependent types to a regular old imperative language. And further, if that's your attitude toward functional programming, I'm sorry.

I should've said "pure functional programming" instead.

ML does, in fact, allow mutable state

typedef struct 
{
     state a;
     int return_1;
     int return_2;
} reply_data;
reply_data pure_functional_function(const state s, const int arg_1, const int arg_2);