-2

Some of the most optimal versions of functions like popcount and count consecutive zeros use table lookups to get the final answer.

In C and C++ one can allocate arrays on the stack and access them quickly.

Is there a way to do this in C# as well? As far as I know, stackalloc can only be used within functions and thus the array won't persist.

I have a small lookup table that I'd like to be able to access as quickly as possible and thus would prefer to allocate it on the stack rather than heap.

trincot
  • 317,000
  • 35
  • 244
  • 286
Ryan Peschel
  • 11,087
  • 19
  • 74
  • 136
  • A local variable with primitive type is allocated on the stack, isn't it? – Thomas Weller Mar 29 '15 at 00:10
  • _"As far as I know, stackalloc can only be used within functions and thus the array won't persist"_ - I'm pretty sure what you ask is not possible. _"**There is no way to explicitly free memory allocated using stackalloc**. All stack allocated memory blocks created during the execution of a function member are **automatically discarded when that function member returns**"_ - _[Tell me more](https://msdn.microsoft.com/en-us/library/aa664785%28v=vs.71%29.aspx?f=255&MSPPError=-2147217396)_. That's what it means to use the local context stack. –  Mar 29 '15 at 00:10
  • *"`stackalloc` can only be used within functions and thus the array won't persist."* Well, that's exactly how the stack works.... I think there must be something about the stack you dodn't understand very well... Why would accessing the stack be faster than the heap? – Lucas Trzesniewski Mar 29 '15 at 00:10
  • I'm never going to free it (just a static array only to be read from) and it's only 32 element anyway. So it's impossible then? Okay. – Ryan Peschel Mar 29 '15 at 00:10
  • 1
    If it's an array you want to be persistent, then it simply *cannot* live on the stack, by definition. – Lucas Trzesniewski Mar 29 '15 at 00:14
  • Hmm that's lame. You'd think there'd be something you could do to an array to make it quicker to access because they can't be constant. – Ryan Peschel Mar 29 '15 at 00:15
  • Nope, that's not lame. That's just the difference between stack and heap. Did you actually measure an actual memory locality/cache miss problem, or is it just some attempt at *very premature* micro-optimization? – Lucas Trzesniewski Mar 29 '15 at 00:17
  • I'm just basing it off of the 12 instruction-based `popcount` being faster than tabular lookup in C# even though it should be the other way around. – Ryan Peschel Mar 29 '15 at 00:19
  • 1
    _"Hmm that's lame. You'd think there'd be something you could do to an array to make it quicker to access because they can't be constant"_ - why don't you just allocate an array the regular way and assign it to a **static field**? –  Mar 29 '15 at 00:39
  • _"stackalloc can only be used within functions and thus the array won't persist"_ -- note that this is exactly the same as e.g. `alloca` in C/C++. I.e. the only way for something you've allocated on the stack to persist is for the function/method in which that something was allocated to not return. As soon as it does, the thing you allocated on the stack is gone. – Peter Duniho Mar 29 '15 at 01:20
  • possible duplicate of [Heap versus Stack allocation implications (.NET)](http://stackoverflow.com/questions/477101/heap-versus-stack-allocation-implications-net) –  Mar 29 '15 at 02:00
  • The premise of the question is wrong; memory is memory, and the stack and the heap use the same RAM to hold objects. Unless you're using some kind of additional pointer indirection to access different objects, accessing one location in memory is no different than any other on modern virtual-memory CPUs. – David R Tribble Nov 09 '15 at 17:17

1 Answers1

5

I have a small lookup table that I'd like to be able to access as quickly as possible and thus would prefer to allocate it on the stack rather than heap.

That statement is confusing. Putting something on the stack means it has to be reinitialized every time you enter the function in which it's declared. The usual "optimization" is to instead store such data in a persistent location, such as a static variable.

For example, here's a sample popcount() implementation from the Hamming weight Wikipedia article:

static uint8_t wordbits[65536] = { /* bitcounts of integers 0 through 65535, inclusive */ };
static int popcount(uint32_t i)
{
    return (wordbits[i&0xFFFF] + wordbits[i>>16]);
}

Note that the wordbits array is declared outside of any function, as a static variable.

A similar declaration in C# would be something like this:

static readonly byte[] wordbits = { /* bitcounts of integers 0 through 65535, inclusive */  };
static int popcount(uint i)
{
    return (wordbits[i & 0xFFFF] + wordbits[i >> 16]);
}

Note the use of C#'s readonly keyword to make clear that this object will only ever be initialized once.

(Obviously, in both examples the comment in the array is replaced by actual values. Alternatively, they can be computed once at runtime and saved into the array).

From your question, it seems like maybe you're at least a little confused about stack vs. heap vs. data segment (i.e. a special range of memory read straight from an executable image into memory). For performance, stack allocations are useful if you're dealing with fixed-sized objects that are allocated frequently and which you don't want to suffer the cost of allocating via the memory manager.

But allocating on the stack doesn't offer any performance benefit in terms of actually accessing the data, and definitely also does not offer any performance benefit in terms of initializing the data. Indeed, on the latter count it would cost you more because you'd have to initialize it each time you enter the function.

I believe that the above ought to adequately address your concern. But if not, please review what it is you're actually trying to do, and edit your question so that it is more clear. You can check How do I ask a good question for advice on how to better present your question in a clear, answerable way.

Peter Duniho
  • 68,759
  • 7
  • 102
  • 136