Dconf 2015 talks...

Joseph Rushton Wakeling via Digitalmars-d digitalmars-d at puremagic.com
Sun Feb 7 14:27:40 PST 2016


On Monday, 25 January 2016 at 22:06:31 UTC, Era Scarecrow wrote:
> On Monday, 25 January 2016 at 21:22:13 UTC, Joseph Rushton 
> Wakeling wrote:
>> I have been wondering about how allocators could help to deal 
>> with these problems.  Could you put forward a minimal example 
>> of how you would see it working?
>
>  Most likely alloca would have to be built into the compiler. 
> Here's a crash course in how the stack memory management works. 
> sp=stack pointer, bp=base pointer (more relevant pre 386).

Apologies for the delay in writing back about this.

What you describe makes sense, but I don't quite follow what you 
mean in one particular case:

>  Technically alloca simply returns the current sp, then adds to 
> it the number of bytes you requested. This means you have to 
> run it at the function stack where you want to use it (and not 
> in a called function, otherwise corruption). So inlined 
> functions where alloca's data would remain would be a must.

I don't quite follow your remark about inlined functions; do you 
mean that the function where the RNG instance is generated must 
be inlined?  (That would make sense in order to avoid the 
internal state being deallocated immediately.)

I think there might be more complications here than just 
allocating individual RNG instances, though (which can happen 
quite early on in the program); what about stuff like random 
algorithms (RandomCover, RandomSample) which might be generated 
deep in internal loops, passed to other functionality as rvalues, 
etc. etc.?

> Then it comes down to a simple:
>
> [code]
> struct RNG {
>   int *state; //add assert to functions that this isn't null
>   this(int seed) {
>     state = alloca(sizeof(int));
>     *state = seed;
>   }
> }
> [/code]

Yes, missing your understanding of the details of how it would 
have to happen, this is pretty much what I had in mind for random 
ranges; a pointer to internal state nevertheless allocated on the 
stack.  But the already-mentioned concerns about some of the ways 
that stack could be deallocated make for some concerns.

It might be simpler, in practice, to just have the state 
refcounted.

>>>  I suppose the alternate is an option to skip/throw-away some 
>>> numbers that should've been consumed (assuming you want to 
>>> keep using the same seed), or seeding each per use.
>>
>> I'm not sure I follow what you mean here or why you think this 
>> would work?  Could you give a concrete example?
>
> certainly.
>
> [code]
> struct RNG {
>   ...
>
>   void skip(int x) {assert(x>0); while(x--) popfront();}
> }
>
> RNG rnd = RND(seed);
> rnd.take(10).writeln;  //loosely based on talk examples
> rnd.skip(10);          //skips the 'consumed' numbers.
> rnd.take(10).writeln;  //won't have identical output
>
> [/code]

I'm afraid that's not really viable :-(  In the best case, it's 
just working around the fundamental design problem via programmer 
virtue.  But the problem is, in the general case, you can't 
anticipate how many random variates may be popped from your 
random number generator inside a function (it might depend on 
other input factors over which you as programmer have no control).


More information about the Digitalmars-d mailing list