www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.bugs - [Issue 9088] New: static static

reply d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=9088

           Summary: static static
           Product: D
           Version: D2
          Platform: All
        OS/Version: All
            Status: NEW
          Severity: enhancement
          Priority: P2
         Component: DMD
        AssignedTo: nobody puremagic.com
        ReportedBy: bearophile_hugs eml.cc



Here I suggest an enhancement for D language (that is pure an addition, it
should cause no breaking changes).

The introduction of "static static", it roughly means "static regarding to the
template". This means that if a template contains a "static static" item, it is
shared among all instantiations of the template.

Here are some use cases:

- - - - - - - - - - - - - -

Templated classes or templated structs sometimes have member functions that are
meant to be shared among all the instantiations of the template.

struct Foo(T) {
    T x;
    static static int sqr(int x) { return x ^^ 2; }
}


Here static static allows to reduce template bloat, because only one sqr()
function is generated regardless the T type. Putting sqr() outside Foo is an
alternative solution, but it loses the packaging given by Foo itself (despite
the usefulness of universal call syntax).

A third solution is to put inside Foo() just a stub function that calls an
external private _sqr() function. This has both the advantage of keeping sqr()
in the the namespace, and keeps the template bloat low because only very little
sqr() are generated for each instantiation of Foo. But this requires parameter
fowarding and increases code complexity a little.

- - - - - - - - - - - - - -

There are cases where templated functions need a static variable that is shared
among all instantiations of the template:

int foo(T)() if (is(T == char) || is(T == dchar) || is(T == wchar)) {
    static static dchar[] table = ['a', 'b', 'c'];
    static static immutable val = someHeavyCTFE(10);
    // uses table and val here
    return 0;
}



In this case static static is useful to save memory, because only one table is
present for all instantiations of Foo. And only one val is computed, saving
compilation time.

An alternative design is to put both table and val outside foo(), but this adds
more global names that are better kept inside foo(), just like a static
variable in a function avoids names at module level.


This example program computes some numbers:


uint topswops(size_t nMax = 16)(in size_t n) nothrow
in {
    assert(n > 0 && n < nMax);
} body {
    size_t d = 0;
    __gshared uint[nMax] best;

    alias T = byte;
    alias Deck = T[nMax];

    void trySwaps(in ref Deck deck, in uint f) nothrow {
        if (d > best[n])
            best[n] = d;

        foreach_reverse (immutable i; 0 .. n) {
            if (deck[i] == -1 || deck[i] == i)
                break;
            if (d + best[i] <= best[n])
                return;
        }

        Deck deck2 = deck;

        d++;
        uint k = 1;
        foreach (immutable i; 1 .. n) {
            k <<= 1;
            if (deck2[i] == -1) {
                if (f & k)
                    continue;
            } else if (deck2[i] != i)
                continue;

            deck2[0] = cast(T)i;
            foreach_reverse (immutable j; 0 .. i)
                deck2[i - j] = deck[j];
            trySwaps(deck2, f | k);
        }
        d--;
    }

    best[n] = 0;
    Deck deck0 = -1;
    deck0[0] = 0;
    trySwaps(deck0, 1);
    return best[n];
}

import std.stdio;

void main() {
    foreach (i; 1 .. 13)
        writefln("%2d: %d", i, topswops(i));
}





To speed up the computation the n argument is now a compile-time value, and
topswops() is a template:


import std.stdio, std.typetuple;

template Range(int start, int stop) {
    static if (stop <= start)
        alias TypeTuple!() Range;
    else
        alias TypeTuple!(Range!(start, stop - 1), stop - 1) Range;
}

__gshared uint[32] best;

uint topswops(size_t n)() nothrow {
    static assert(n > 0 && n < best.length);
    size_t d = 0;

    alias T = byte;
    alias Deck = T[n];

    void trySwaps(in ref Deck deck, in uint f) nothrow {
        if (d > best[n])
            best[n] = d;

        foreach_reverse (immutable i; Range!(0, n)) {
            if (deck[i] == -1 || deck[i] == i)
                break;
            if (d + best[i] <= best[n])
                return;
        }

        Deck deck2 = void;
        foreach (immutable i; Range!(0, n)) // Copy.
            deck2[i] = deck[i];

        d++;
        foreach (immutable i; Range!(1, n)) {
            enum uint k = 1U << i;
            if (deck2[i] == -1) {
                if (f & k)
                    continue;
            } else if (deck2[i] != i)
                continue;

            deck2[0] = cast(T)i;
            foreach_reverse (immutable j; Range!(0, i))
                deck2[i - j] = deck[j]; // Reverse copy.
            trySwaps(deck2, f | k);
        }
        d--;
    }

    best[n] = 0;
    Deck deck0 = -1;
    deck0[0] = 0;
    trySwaps(deck0, 1);
    return best[n];
}

void main() {
    foreach (i; Range!(1, 13))
        writefln("%2d: %d", i, topswops!i());
}



To work correctly this program requires a static variable "best". Once
topswops() becomes a template, "best" must be moved to module scope. This is
avoided by static static:

...
uint topswops(size_t n)() nothrow {
    static assert(n > 0 && n < best.length);
    size_t d = 0;
    static static __gshared uint[32] best;
...

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Nov 27 2012
next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=9088


Andrej Mitrovic <andrej.mitrovich gmail.com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |andrej.mitrovich gmail.com



05:15:58 PST ---
For functions: I think this might be the job of the compiler/linker. If there
are multiple static function definitions that are identical they should be
merged, there's no need for the user to do the job of the compiler/linker.

As for template-shared variables, they are possible without bloating the global
(module) scope by using templates, for example:

template Wrap()
{
    int globX;

    struct Foo(T)
    {
        alias globX x;
    }
}

alias Wrap!().Foo Foo;

void main()
{
    Foo!(int) f1;
    Foo!(float) f2;

    f1.x = 10;
    assert(f2.x == 10);
}

You could probably implement some kind of helper mixin that could implement
this automatically.

Here's the same trick with function templates:

import std.stdio;

template Wrap()
{
    dchar[] table = ['a', 'b', 'c'];
    immutable val = 10;

    int foo(T)() if (is(T == char) || is(T == dchar) || is(T == wchar))
    {
        writeln(&table);
        return 0;
    }
}

alias Wrap!().foo foo;

void main()
{
    alias foo!char fooChar;
    alias foo!dchar fooDChar;

    // both print the same address
    fooChar();
    fooDChar();
}

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Nov 29 2012
prev sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=9088






Thank you for the answers Andrej.


 For functions: I think this might be the job of the compiler/linker. If there
 are multiple static function definitions that are identical they should be
 merged, there's no need for the user to do the job of the compiler/linker.


Notes:
- Currently DMD is not doing this, and I think it's not going to do it soon (I
don't know about GDC2, possibly GCC is able to do this, but see below);
- I think LDC2 is able to do this, but you have to add a compilation switch
that is not included in "-O4" switch and that no one uses or knows about
(something avout merging functions);
- I think in C if you have many different functions that contain the same code,
and you take their address, the C language requires them to be different. I
assume D shares the same C rule. So LDC is forced to leave stubs that contain a
jump, it can't delete them fully;
- Avoiding to create bloat in the first place is faster for the compiler+linker
than compiling them and then not linking them (or recognizing them as equal and
replacing them with a jump to just one implementation). I agree that in theory
the compiler can avoid creating those copies in the first place, because it
knows they come from a template, but I think currently LDC2 is not this smart;
- A "static static" annotation is a contract between compiler and programmer,
like "pure". This means that if you try to use the template arguments (that are
types and compile-time values) in a "static static" template struct method, the
compiler complaints at compile-time (something similar happens if you try to
use a locally defined variable in a static nested function). This enforcing
can't happen if such feature is left to compiler/linker optimizations.
- Generally I think D needs somethiong to help fight template bloat. "static
static" is not very good for this, but I think it helps.



 As for template-shared variables, they are possible without bloating the global
 (module) scope by using templates, for example:
 ...
 You could probably implement some kind of helper mixin that could implement
 this automatically.


"static static" is not essential, because there's always the possibility to
move things to module scope.

On the other hand if you take a look at topswops(), a "static static"
annotation allows to minimize the amount of changes in the code when you want
to turn a function into a template (and avoid moving static variabiles to
globals). So it's not essential, but I think it's handy, in some cases.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Nov 29 2012