Speeding Up Function Lookups

[Valik]

The downside would likely be that every other "sane" compiler would promptly bitch about too many braces or get confused with the extra set of braces. That basically means that if that is indeed the problem, it's circular in it's effect. Though fixable with clever #ifdef's, I guess....

Perhaps this is something that isn't implemented in VC6 (Although I would surely like to think it is by SP6...).

[Gene]

The downside would likely be that every other "sane" compiler would promptly bitch about too many braces or get confused with the extra set of braces.  That basically means that if that is indeed the problem, it's circular in it's effect.  Though fixable with clever #ifdef's, I guess....

Perhaps this is something that isn't implemented in VC6 (Although I would surely like to think it is by SP6...).

Wouldn't that either confirm your diagnosis, or leave you still in the dark? I have to go lie down now, talking over my head makes me dizzy.

Gene

[Jon]

Perhaps this is something that isn't implemented in VC6 (Although I would surely like to think it is by SP6...).

There are mutterings on google about this problem, but I've not found an exact match yet. I am using SP5 (looks like SP6 only came out last week) - I'll have to wait until tonight to download it as it's 60MB and I'm on dialup at work.

Even this doesn't work:

#include <iostream>
#include <string>


struct info
{
   std::string name;
};

class Test
{
public:

   static info list[];
};

// This definition could be in another file, the linker will find it.
info Test::list[] = {
   {"Betsy"}  
};

I tried the same thing with a simple "int" and it was OK, but with std::string I get the same error.

[Jon]

I changed the AString sName definition to a default char[20] declaration (meaning that there are now no constructors required in the struct - seems to be a VC6 bug) and that compiled.

But.

The change gives a code size increase of 20KB!!!!! Back to the giant "case" statement I think This is doubly annoying as I spent so much time rewriting all the functions to have standard parameters. I may leave those changes in and modify the case statement to use them.

[Valik]

I don't understand why it would be so much larger. You stored all that data already (Except the pointer), so where is the huge size increase coming from? You even eliminated the entire case structure which should of actually caused things to be less.

[Jon]

No idea. I assume that whatever stuff is done to resolve those function pointers at runtime is not as simple as appears.

Under VC7 when I had it with the char[20] declaration it was 235KB, with the AString instead it was 215KB, so maybe if the VC6 version could have used an AString without the compiler complaining it would have been smaller.

Edit:

More of the case stuff was inlined than I thought too, so I probably created about 30 new functions, but they are all one or two liners. I woudn't have thought that 30 functions declarations causes such an increase. I'm sure I'll find out, i'll modify the case statement to use the new function calls. If the size stays large then that will answer the question.

Edited May 10, 2004 by Jon

[tylo]

I think 30 non-inlined funcs would add quite a bit of code. Inlined 2-liners generates virtually no exe code - the functions takes 0 bytes, and the amount of code created by calls (expanding inlined code) is less than the code created by calling the non-inlined versions.

As an experiment, could you try to make the func_list non-static? (you'll have to remove the initialization for a moment). Does that make the exe smaller? If so, you can initialize a local stack variable of func_list in the constructor (the same way as the static one), and then copy that to the member variable.

The static function pointer resolution itself shouldn't increase the exe size, so it should at least not generate more code than the switch block. Hope this helps.

Edited May 10, 2004 by tylo

[Jon]

If I turn off linker optimizing (so that unused stuff doesn't get optimized out during this test):

With all the functions declared and initialized in the FuncList static variable I get an exe size of 245KB. If I just initialize a couple I get 215KB. Which says to me that the static declaration is the culprit rather than the extra functions I added.

[Valik]

You can always generate the function list at run time. A few pre-processor macro's could allow you to generate a list like this:

BEGIN_FUNCTION_MAP(AutoIt_Script)
    REGISTER_FUNCTION("Random", 0, 1, Random)
    // ...
END_FUNCTION_MAP

And then at compile time it's translated to some code that builds the list of functions at run time.

The code for those macro's might be:

#define BEGIN_FUNCTION_MAP(theClass) \
    theClass::RegisterAll() \
    {

#define REGISTER_FUNCTION(name, min, max, func) Register(name, min, max, func);

#define END_FUNCTION_MAP }

The actual Register function is basically a push_back() I guess. However you want to build the list, really.

At any rate, if using that, then in the Constructor or just after creation but before attempting to do anything with the AutoIt_Script object, call RegisterAll().

That would add some initial overhead at run-time, but it should reduce the compiled size since it's not using anything static and it should also make up for itself later on when the function lookup is faster.

[tylo]

Here's what I meant. Try:

class AutoIt_Script;       // Forward declaration

typedef AUT_RESULT (AutoIt_Script::*AU3_FUNCTION)(VectorVariant &vParams, uint iNumParams, Variant &vResult);

typedef struct  
{
   char   szName[20];     // Function name 
   AU3_FUNCTION lpFunc;      // Pointer to function
   uchar   cMin;      // Min params
   uchar   cMax;      // Max params    
} AU3_FuncInfo;
 

class AutoIt_Script
{
   ....
   AU3_FuncInfo* m_FuncList;
   int m_nFuncs;

};


AutoIt_Script::AutoIt_Script()
{
   AU3_FuncInfo funcList[] = {
   {"ADLIBDISABLE", F_AdlibDisable, 0, 0},
   {"ADLIBENABLE", F_AdlibEnable, 1, 2},
    ...
  };
  m_nFuncs = sizeof(funcList) / sizeof(AU3_FuncInfo);
  m_funcList = new AU3_FuncInfo[m_nFuncs];
  //for (int i=0; i<m_nFuncs; ++i) m_FuncList[i] = funcList[i];
  memcpy(m_funcList, funcList, sizeof(funcList));
}

/ADD: My testing indicates that this should do the trick.

Edited May 10, 2004 by tylo

[Jon]

I'll give it a try tomorrow... 10:15pm and only just in from work. What a shite week.

[Jon]

Edit: 206KB with that method (compressed = 92KB) (Old version 88.5KB)

The question is, is it worth the extra size....

Edited May 11, 2004 by Jon

[Nutster]

I think the size increase might be happening because of all the constructor calls that are being written. What about this?

class AutoIt_Script;       // Forward declaration

typedef AUT_RESULT (AutoIt_Script::*AU3_FUNCTION)(VectorVariant &vParams, uint iNumParams, Variant &vResult);

typedef struct  
{
  char   *szName;     // Function name
  AU3_FUNCTION lpFunc;      // Pointer to function
  uchar   cMin;      // Min params
  uchar   cMax;      // Max params    
} AU3_FuncInfo;

static const AU3_FuncInfo AutoIt_Script::funcList[] = {
  {"ADLIBDISABLE", F_AdlibDisable, 0, 0},
  {"ADLIBENABLE", F_AdlibEnable, 1, 2},
   ...
};

This will remove all the constructor calls for each element of the list, and will store each string in an optimal space.

Edit: Oh, yeah (just re-read the stream) This may still cause a problem in VC6. I will investigate tonight on my VC6 SP6.

Edited May 11, 2004 by Nutster

[Jon]

Oo, actually changing the char[20] to char * drops the size by another 2KB to 90.5 KB.

[Valik]

I have another idea as well. Instead of using 2 parameters for the min/max, why not use a WORD and put min in one BYTE and max in the other BYTE? The parameters are only used in one or two places, so it isn't that big of a deal to get them back out with HIBYTE and LOBYTE.

It's very easy to write a #define to do that. I used LONG in this example, but WORD's and BYTES will also work.

#define MOO(n, x, y) { n, MAKELONG(x, y) }

struct temp
{
    std::string name;
    LONG params;
};
static temp test[] = {
    MOO("cool", 1, 2),
    MOO("Wow!", 3, 4)
};

std::cout<<test[0].name<<" - "<<HIWORD(test[0].params)<<
    " - "<<LOWORD(test[0].params)<<std::endl;
std::cout<<test[1].name<<" - "<<HIWORD(test[1].params)<<
    " - "<<LOWORD(test[1].params)<<std::endl;

[Jon]

Hmm, thinking about it, if I use char * for the name then I can;t use Tylo's code of :

for (int i=0; i<m_nFuncs; ++i) m_FuncList[i] = funcList[i];

As that won't copy the char * component correctly, yes? I will just have to copy the elements individually.

Edit: something like:

for (i=0; i<m_nFuncListSize; ++i) 
    {
  //m_FuncList[i] = funcList[i];
  m_FuncList[i].szName = new char[strlen(funcList[i].szName) + 1];
  strcpy(m_FuncList[i].szName, funcList[i].szName);
  m_FuncList[i].lpFunc = funcList[i].lpFunc;
  m_FuncList[i].cMin = funcList[i].cMin;
  m_FuncList[i].cMax = funcList[i].cMax;
    }

Edited May 11, 2004 by Jon

[tylo]

Jon, forget my code ( but your suggestion was correct).

@Nutster: I believe your suggestion gives the smallest exe. However a small quirk with your current suggestion is that it is not possible to have a static member array with unknown length. You must simply define a static local s_FuncList in AutoIt_Script.cpp:

(hmm. we're back to were we started, only Astring -> char* member apart).

typedef AUT_RESULT (AutoIt_Script::*AU3_FUNCTION)(VectorVariant &vParams, uint iNumParams, Variant &vResult);

struct  AU3_FuncInfo
{
 char   *szName;     // Function name
 AU3_FUNCTION lpFunc;      // Pointer to function
 uchar   cMin;      // Min params
 uchar   cMax;      // Max params    
};

----- AutoIt_Script.cpp: -----

static const AU3_FuncInfo s_FuncList[] = {
 {"ADLIBDISABLE", F_AdlibDisable, 0, 0},
 {"ADLIBENABLE", F_AdlibEnable, 1, 2},
  ...
};
static const int s_nFuncListSize = sizeof(s_FuncList)/sizeof(s_FuncList[0]);

// ...code using s_FuncList, s_nFuncListSize here. or define access funcs:

AU3_FuncInfo* AutoItScript::FuncList() const { return s_FuncList; }
int AutoItScript::nFuncListSize() const { return s_nFuncListSize; }

Edited May 12, 2004 by tylo

[Nutster]

Actually the length of the structure is known. The pointer (char *) is a standard size (4 bytes I think), each of which is pointing into a series of string literal constants in the .TEXT space of the executable. All string literal are stored in this space, whose size is determined at linking-time.

As far the AString comparison: Get the actual string and compare it to do the search.

int i, k;

for (i=0; s_FuncList[i][0] != '\0'; ++i) {
   k=strcmp(sParsedFuncName.c_string(), s_FuncList[i].szName);
   if (k<0)
      // go down
   else if (k>0)
     //  go up
   else
     // match.  Check argument counts and call the function
}

[tylo]

You're right. Not important, but I meant the lenght of the array is unknown before it's defined. And it is impossible to pre-declare an array of unknown length, e.g.:

class AutoIt_Script {
   static const AU3_FuncInfo m_FuncList[]; // is illegal
};

You could define it in the header file, but every .cpp file that include it would then have a copy of it. (some smart linkers can optimize that away). If you really want a FuncList member, you can do:

class AutoIt_Script {
   static const AU3_FuncInfo *m_FuncList;
};

--- AutoIt_Script.cpp: ---
static const AU3_FuncInfo s_FuncList[] = { ... };
const AU3_FuncInfo *AutoIt_Script::m_FuncList = s_FuncList;

Edited May 13, 2004 by tylo

[Nutster]

This may still cause a problem in VC6.  I will investigate tonight on my VC6 SP6.

Damn! Making an array of structs/classes using aggregate notation does not work under VC6. Damn but that is a weird error message. They could just say that arrays of classes can not be initilized this way.

Hmm, make a binary tree of the class and then store them in the constructor of the script class.

// a desperate attempt to get away from a huge case statement and make it easier to manage.

FuncCall.add("ADLIBDISABLE", F_AdlibDisable, 0, 0);
FuncCall.add("ADLIBENABLE", F_AdlibEnable, 1, 2);
...
FuncCall.balance();

Oh, yeah, I am supposed to check if the linked list vs. binary tree vs. array for speed. Maybe this weekend.