1

I have implemented a fast comparison function which uses a look-up table. Since this function is used in multiple classes in the project, I need to make sure that there is only one copy of the look-up table during the whole execution of the program.

The look-up table is a simple vector<int> of size 65536. I wish that this table is initialized at the beginning of the program, not at the time of its first use. How to deal with this problem?

The following code snippet is the current version of my comparison function. I believe that by making lookup_table a static variable, the problem will be resolved only partially, because the lifetime of static variables begins the first time the program flow encounters the declaration.

int fast_compare(const char* array1, const char* array2, int length)
{
    static const vector<int> lookup_table = init_lookup_table();

    // process the input arrays...
    // ...
    return lookup_table[...];
}

vector<int> init_lookup_table()
{
    vector<int> lut(65536);

    // ----------------------------
    // initialize the look-up table
    // ...
    // ...
    // end of initialization
    // ----------------------------

    return lut;
}
enzom83
  • 8,080
  • 10
  • 68
  • 114
  • 1
    If you know the size at compile-time, you can benefit from using `std::array` instead of `std::vector`. – Zyx 2000 Apr 14 '13 at 22:25
  • 1
    Declaring `lut` as a `static` variable in the `fast_compare` function would make it much more thread-safe. You could prime the variable with a call to the function at start-up if you require predictable runtime. – Benjamin Bannier Apr 16 '13 at 11:57
  • My comment on thread-safty applies to C++11 only, see paragraph 6.7.4 there. – Benjamin Bannier Apr 16 '13 at 12:17

2 Answers2

6

I wish that this table is initialized at the beginning of the program, not at the time of its first use.

Why not use a un-named namespace in the cpp file?

#include <numeric>
#include <iterator>
#include <iostream>
#include <vector>

namespace {
    //c++11 version
    static auto const lookup_table = []() -> std::vector<int> { 
        std::vector<int> lut(65536);
        iota(begin(lut), end(lut), 0);// init lut here
        return lut;
    }();// invoke the lambda

    //c++ 98 version
    //static const std::vector<int> lookup_table = init_lookup_table();
}

int main()
{
    std::cout<<"lut[32768] = " << lookup_table[32768]<<std::endl;
}

The lambda initialization is explained by Herb Sutter here

indeterminately sequenced
  • 626
  • 6
  • 17
  • 1
    @ypnos I have added a C++98 version. The benefit of the lambda is that you have no *named* function rather just a block of initialization code associated with the global. – indeterminately sequenced Apr 16 '13 at 11:45
2

What you describe is the Singleton pattern. There exist documentation on the web on how a singleton is typically implemented with C++.

Basically it is a small class that bears a static function which returns pointer/reference to the lookup table (me, personally, I prefer references).

Reference: Singleton: How should it be used

However, a simpler solution to your specific problem could be to just generate the lookup table once, then hand boost::shared_pointers around.

Community
  • 1
  • 1
ypnos
  • 50,202
  • 14
  • 95
  • 141
  • Ok, but how to ensure that the look-up table is allocated before it is used? If this table is very large, then the first call to the `fast_compare()` function could be performed slowly, because the table would be allocated the first time the program flow encounters the declaration. I wish the table to be allocated earlier than the first call to `fast_compare()`. – enzom83 Apr 15 '13 at 19:40
  • 1
    You can always do a single query at the beginning and not use the result of that query. Or you could try a static class variable. – ypnos Apr 16 '13 at 09:03