Tail pad optimization, cache friendlyness and C++ interrop

H. S. Teoh via Digitalmars-d digitalmars-d at puremagic.com
Thu Jun 19 11:48:50 PDT 2014


On Thu, Jun 19, 2014 at 06:24:59PM +0000, Tobias Pankrath via Digitalmars-d wrote:
> On Thursday, 19 June 2014 at 04:06:51 UTC, Ola Fosheim Grøstad wrote:
> >On Wednesday, 18 June 2014 at 21:57:40 UTC, deadalnix wrote:
> >>Granted infinite resources. Good, now that we ruled that thing out,
> >>can we talk about the subject, or do we need to continue talking
> >>about imaginary things ?
> >
> >No, finite resources, and that is only a worst case upper bound. It
> >does not preclude the possibility of doing better. It also does not
> >say how much work it is in the typical case e.g. the kind of programs
> >you wrote when you try to make code @safe.
> >
> >What it does prove is that the problem is computable, that is a major
> >difference. Please note that the halting problem does not address
> >difficulty but analytical computability.
> >
> >In the real world you work with typical programs that run on finite
> >resources guided by heuristics. There is no proof that you cannot
> >have @safe. So leave that line of arguing. It is fundamentally
> >flawed.
> 
> It's not. Since the resources to verify a property are limited, too.
> 
> If I need to enumerate all possible program states, there will always
> exists a program that can run on my box but will not be verifiable on
> it (since I lack the resources).
> 
> It's also not enough for @safe to be verifiable, it should not slow
> down the compilation time too much as well.

Exactly.  Just because something is *finite*, doesn't necessarily mean
it's practical.  Anything that requires enumeration of all possible
states is impractical, because it has an exponential worst case bound,
which is unacceptable for compilation time (or for anything, really,
except in the most trivial cases).

To get an idea of how intractible it can get, suppose your entire
program state is fully described by, say, 1 MB worth of variables
(that's pretty conservative, considering the size of programs these days
and the size of the data they deal with). The upper bound to enumerating
all program states is 2^(1 MB) = 2^2^20 = ... (a number with 324,936
digits). Note that that's not 324,936 *states*, but that's the number of
*digits* in the number of states! It's a finite number, sure, but good
luck enumerating all program states within the lifetime of the universe
(don't even talk about within your lifetime!).

Even if you run it on a hypothetical distributed supercomputer with 100
billion nodes, that barely even begins to make a dent in the number of
states you need to evaluate (the number of states per node is a number
with "only" 324,925 digits, haha).

And mind you, 1 MB of state is pathetically small. Real programs these
days require GB's of memory, and that will cause the number of states to
explode far, far beyond any imaginable computing capabilities of the
human race, past, present, or future -- unless we manage to invent a
device that exploits time contraction near a black hole's horizon to
compute the halting problem in finite time (i.e., it's pure fiction).


T

-- 
Question authority. Don't ask why, just do it.


More information about the Digitalmars-d mailing list