4 ms·

>the optimization step to not initialize those variables that are written to before used doesn't seem so far away Determining whether or not variables will be

by xamuel 12y ago

>the optimization step to not initialize those variables that are written to before used doesn't seem so far away Determining whether or not variables will be used uninitialized is equivalent to solving the halting problem.

pkolaczk 12y ago
In general case only. For most of typical code, it is quite obvious. If your program makes initialization depend on many conditions which makes it hard to analyze for the compiler, you're probably writing very fragile code that will soon bite you with UB.
- haberman 12y ago
  > For most of typical code, it is quite obvious. [citation needed] > If your program makes initialization depend on many conditions which makes it hard to analyze for the compiler, you're probably writing very fragile code that will soon bite you with UB. Say you allocate a stack, and access it with the following pattern: bool push(stack *st) { if (st->top == st->limit) return false; st->top++; st->top->foo = FOO_INIT; st->top->bar = BAR_INIT; return true; } void pop(stack *st) { assert(st->top != st->stack); st->top--; } void stack_alloc(stack *st, int n) { st->stack = malloc(n * sizeof(*st->stack)); st->top = st->stack; st->limit = st->stack + n - 1; } If you only access the stack through st->top, it is easy to see (for a human) that the stack will never be accessed uninitialized. Good luck getting the compiler to build an inductive proof of that though. This is just the first example that popped into my mind because I was doing this yesterday.
  - pkolaczk 12y ago
    I said most, not every. int x; .... x = 5; printf("%d\n", x); Anyway, in you code the cost of malloc is a lot higher than the cost of zeroing out. And I guess most of the time it is hard to elide variable initialization would be in places where you have non-local variable use and you do heap allocation.
    - haberman 12y ago
      > Anyway, in you code the cost of malloc is a lot higher than the cost of zeroing out. You can't possibly know that. The cost of malloc() is (roughly) independent of the size of the memory, and the cost of zeroing it is linear in the size of the memory. So there's an inflection point where zeroing the memory becomes more expensive than the malloc() itself.
      - pkolaczk 12y ago
        Point taken, however in practice this point is quite high to not matter that much. At least in these benchmarks zeroing out is typically responsible for less than 10% of total time overhead, and this including the fact the benchmarked VMs didn't do any zeroing-out elision: http://www.cs.utexas.edu/users/mckinley/papers/zero-oopsla-2011.pdf http://www.cs.utexas.edu/users/mckinley/papers/zero-oopsla-2... I was mostly talking about general variable initialization, not just huge arrays - and for any case "hard" like yours (but actually not impossible to elide; state-machines and inductive proofs are not a rocket surgery) - you've got several trivial cases like I posted above which can be solved by simple local data-flow analysis. This is the same like with NP-hard problems. Some people get scared by NP-hard, but it only matters if you need an exact solution, and is not a problem in practice if you're ok with a result at 0.95 of the optimum. It is also sometimes more time-effective to reuse huge arrays to work around obligatory variable initialization done by the runtime for rare cases where it would be a performance problem, than to fight UBs in 10s of other places where performance doesn't matter.
ArkyBeagle 12y ago
Not if you can initialize them at the time of declaration. IMO, that should be the default policy, and there should be ample comments apologizing for not doing it. People don't build unterminated communications lines nor use PIO without pullups/pulldowns. Programmers should be the same way. Perhaps I've led a charmed life, but I've never seen a case where proper initialization was a problem.

by xamuel 12y ago

pkolaczk 12y ago

In general case only. For most of typical code, it is quite obvious. If your program makes initialization depend on many conditions which makes it hard to analyze for the compiler, you're probably writing very fragile code that will soon bite you with UB.

haberman 12y ago
> For most of typical code, it is quite obvious. [citation needed] > If your program makes initialization depend on many conditions which makes it hard to analyze for the compiler, you're probably writing very fragile code that will soon bite you with UB. Say you allocate a stack, and access it with the following pattern: bool push(stack *st) { if (st->top == st->limit) return false; st->top++; st->top->foo = FOO_INIT; st->top->bar = BAR_INIT; return true; } void pop(stack *st) { assert(st->top != st->stack); st->top--; } void stack_alloc(stack *st, int n) { st->stack = malloc(n * sizeof(*st->stack)); st->top = st->stack; st->limit = st->stack + n - 1; } If you only access the stack through st->top, it is easy to see (for a human) that the stack will never be accessed uninitialized. Good luck getting the compiler to build an inductive proof of that though. This is just the first example that popped into my mind because I was doing this yesterday.
- pkolaczk 12y ago
  I said most, not every. int x; .... x = 5; printf("%d\n", x); Anyway, in you code the cost of malloc is a lot higher than the cost of zeroing out. And I guess most of the time it is hard to elide variable initialization would be in places where you have non-local variable use and you do heap allocation.
  - haberman 12y ago
    > Anyway, in you code the cost of malloc is a lot higher than the cost of zeroing out. You can't possibly know that. The cost of malloc() is (roughly) independent of the size of the memory, and the cost of zeroing it is linear in the size of the memory. So there's an inflection point where zeroing the memory becomes more expensive than the malloc() itself.
    - pkolaczk 12y ago
      Point taken, however in practice this point is quite high to not matter that much. At least in these benchmarks zeroing out is typically responsible for less than 10% of total time overhead, and this including the fact the benchmarked VMs didn't do any zeroing-out elision: http://www.cs.utexas.edu/users/mckinley/papers/zero-oopsla-2011.pdf http://www.cs.utexas.edu/users/mckinley/papers/zero-oopsla-2... I was mostly talking about general variable initialization, not just huge arrays - and for any case "hard" like yours (but actually not impossible to elide; state-machines and inductive proofs are not a rocket surgery) - you've got several trivial cases like I posted above which can be solved by simple local data-flow analysis. This is the same like with NP-hard problems. Some people get scared by NP-hard, but it only matters if you need an exact solution, and is not a problem in practice if you're ok with a result at 0.95 of the optimum. It is also sometimes more time-effective to reuse huge arrays to work around obligatory variable initialization done by the runtime for rare cases where it would be a performance problem, than to fight UBs in 10s of other places where performance doesn't matter.

ArkyBeagle 12y ago

Not if you can initialize them at the time of declaration. IMO, that should be the default policy, and there should be ample comments apologizing for not doing it. People don't build unterminated communications lines nor use PIO without pullups/pulldowns. Programmers should be the same way. Perhaps I've led a charmed life, but I've never seen a case where proper initialization was a problem.