1

When you have a function that accepts an array as an argument and calls another function with that array and that calls another function with it and so forth the stack will contain many copies of the pointer to that array. I just thought of an interesting way to alleviate this problem but I'm wondering whether or not it is worth implementing.

Does anyone have any idea how often stacks contain duplicate pointers in practice?

EDIT

Just to clarify, I am not optimizing a given program but, rather, am considering writing a new kind of optimization pass for my VM. My benchmarks have indicated that my current solution causes up to 70% of the total running time to be spent in stack manipulations. The optimization pass I am thinking of would generate code at compile time that would perform the same actions but pointers would (potentially) be duplicated on the stack less often. I am interested in any prior studies that have measured the number of duplicates on the stack because this would help me to quantify my optimization's potential. For example, if it is known that real programs do not push pointers already on the stack in practice then my optimization is worthless.

Moreover, these stack manipulations are due to the code generated by my VM making sure locally-held pointers are visible to the garbage collector and not due only to function parameters as both answerers have currently assumed. And they are actually operations on a shadow stack rather than the main stack.

6
  • Depends on the calling convention (hence also the machine architecture) and whatnot, but yes generally each function call will get its own parameters. But why do you think that's any problem at all? We're talking about a 4-8byte here, that's uninteresting except maybe in the most memory constrained embedded systems (and those usually pass most arguments in regs anyhow).
    – Voo
    Apr 1, 2012 at 14:34
  • @Voo My benchmarks indicate that stack manipulations can account for up to 70% of the total running time of a program with my VM. If I can alleviate that (by not pushing references I know I've already pushed) then those programs might run several times faster. But I've no idea how advantageous this would be in real software so I'm wondering if anyone has ever studied duplication on the stack. flyingfrogblog.blogspot.co.uk/2009/03/…
    – J D
    Apr 1, 2012 at 18:14
  • Your program is really spending 70% of its time pushing and popping parameters onto the stack? That's pretty surprising - usually you'd expect small functions to be inlined (which avoids the problem altogether) and larger functions to do enough work that pushing/popping would be amortized.
    – Voo
    Apr 1, 2012 at 19:42
  • @Voo Ah, you're assuming this is just parameters. It isn't. This is about pushing locally-held references onto the stack so the garbage collector will treat them as global roots. Any reference that is acquired (parameters, allocations and pointers read from the heap) get pushed. My VM already unrolls functions which amortizes parameters (as you say) but not the other sources of stack pushes.
    – J D
    Apr 1, 2012 at 20:04
  • @JonHarrop You are kind of answering your own question in your first sentence, aren't you? Arguments tend to be repeated on the stack, especially for OO code. When it comes to non-argument things, I still think you might get more/better answers if you limit the scope of your question to vm and gc.
    – Joh
    Apr 2, 2012 at 14:02

2 Answers 2

2

First of all, the answer will depend on your application.

Secondly, even with high duplication, I doubt there is much sense in implementing the mechanism you describe, or even that it is possible in a general case. If you call a method and you pass it parameters, you must do it either one way or another.

There may be advantages to doing it in some specific way - for example there are several function calling conventions and many C/C++ compilers (e.g. gcc) let you choose between passing parameters on the stack or via registers. In certain cases, the latter may be faster - you can try and benchmark if it helps your application.

But in a general case, the cost of detecting duplicated values on the stack and "reusing" them would probably much exceed any gains from having a smaller stack. The code for pushing and popping values is really simple (just a few CPU instructions in an optimized case), code for finding and reusing duplicates - hardly so. You would also have to somehow store the information about which values are already on the stack and how to find them - a nontrivial data structure. Except for some really weird cases, I don't think this would be smaller than the actual copied data itself.

What you could do, would be to rewrite your algorithm in such way that some function calls are eliminated. For example, if your function's result only depends on the input arguments, you could somehow cache or memoize the results, thus avoiding repeated calls with the same values. This may indeed bring some gains, though it's usually a memory vs CPU time tradeoff. Getting an advantage both in memory and in CPU time is rarely possible. Also, rewriting your algorithm is not really "avoiding duplication of data on the stack".

Any way, for the original question, I think the idea is not viable and you should look at optimizations elsewhere.

PS: You use case may somewhat resemble tail-call optimization, so perhaps that's a direction worth looking at - but if you implement it yourself, I would also consider this to fall into the "change your algorithm" category. Maybe changing from a recursive algorithm to an iterative one could help also.

5
  • Interesting answer but there are lots of misconceptions. You assumed I am talking about optimizing a specific program but I am (thinking about) writing an optimization pass for a VM that will optimize a whole class of programs automatically. You assumed that stack pushes are to function arguments but they are often also due to locally-held registers being stored as global roots for the GC. You assumed I will search for duplicates at run-time (obviously too slow, as you say) but my idea is actually to rewrite the source program before compilation in order to evade unnecessary stack operations.
    – J D
    Apr 1, 2012 at 22:29
  • 1
    +1 @Jon: If I could try to put what Michał is saying another way: If the cost of stack operations is significant in realistic programs then it's worth thinking about. An easy test of this is, when debugging realistic programs (not artificial ones), if you were to pause it at random 20 times, if you found it more than once in the process of doing that. Apr 2, 2012 at 14:52
  • @MikeDunlavey I'm asking this question because I already obtained results that indicate that stack operations can dominate performance. en.wikipedia.org/wiki/Teaching_grandmother_to_suck_eggs
    – J D
    Apr 2, 2012 at 18:06
  • 1
    All I'm saying, @Jon, is of your benchmarks, the one closest to reality is gc. TenQueens is an example of an algorithm that does recursion and very little else. It doesn't extrapolate. In the link I gave in my much-maligned answer :) the program tells me to fix something, & I get 50%. Then it tells me something else, & I get another %. This repeats about 6 times before I stop, having gotten 730x speedup. One of those along the way might have been stack-related. The % it costs depends on where in the sequence it is measured. Apr 2, 2012 at 18:39
  • @MikeDunlavey If the "gc" benchmark is closest to your reality then you're already set with HLVM because it provides excellent performance on that benchmark (and programs like it). However, many people want to use HLVM for functional programming where the "n-queens" benchmark is much more representative of typical code (lots of recursion and allocation of small purely functional data structures) including logic programming, computer algebra and interpreters/compilers. HLVM can be 10x slower than OCaml here. Shadow stack ops are a significant part of this.
    – J D
    Apr 2, 2012 at 20:55
-1

Can I suggest getting some exposure to actual performance tuning? (Here's my canonical example.)

Between the time a program starts and the time it ends, of the cycles it uses, it obviously uses 100% of those cycles. If it goes in and out of functions, and passes pointers to an array, but does nothing else, then there's no surprise that a high percent of time goes into function entry and exit, and passing arguments.

If a program P is written to do task T, there are a multitude of other programs P' which could also do task T. Some of them take fewer cycles than all the others, and those are the optimal ones. The way the optimal ones differ from the non-optimal ones is that the non-optimal ones are doing things that can be done without.

So, to optimize any program, find out what cycles are being spent that don't have to be, and get rid of those activities. That link shows in great detail how I do it.

Trying to pass fewer arguments to functions might or might not be necessary, depending on what your diagnostics tell you.

2
  • @Andrej: I probably could have said it better, but I see entirely too much of people approaching performance as picking an a-priori issue and lasering-in on it, rather than letting the particular program tell them where to look. Apr 2, 2012 at 14:38
  • @MikeDunlavey Please reread the question and my subsequent comments. I have now explained several times why that is not the case.
    – J D
    Apr 2, 2012 at 18:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.