Topic: Yikes! Game.DoOnceOnly implementation!

[monkey0506]

This recent post in the Beginner's forum got me thinking about the implementation of Game.DoOnceOnly, and I came across this:

Code: C++

1. int Game_DoOnceOnly(const char *token)
2. {
3.     if (strlen(token) > 199)
4.         quit("!Game.DoOnceOnly: token length cannot be more than 200 chars");
5.  
6.     for (int i = 0; i < play.num_do_once_tokens; i++)
7.     {
8.         if (strcmp(play.do_once_tokens[i], token) == 0)
9.         {
10.             return 0;
11.         }
12.     }
13.     play.do_once_tokens = (char**)realloc(play.do_once_tokens, sizeof(char*) * (play.num_do_once_tokens + 1));
14.     play.do_once_tokens[play.num_do_once_tokens] = (char*)malloc(strlen(token) + 1);
15.     strcpy(play.do_once_tokens[play.num_do_once_tokens], token);
16.     play.num_do_once_tokens++;
17.     return 1;
18. }

Yikes!

I don't think that CJ was using anything (at all) from the TR1 namespace, but C++11's unordered_set is available with VS2008 in the TR1 namespace (which I know is now used in some places), and seems like it would be vastly more efficient for this.

The implementation could simply be changed to:

Code: C++

1. #include <unordered_set>
2. #include <string>
3.  
4. int Game_DoOnceOnly(const char *token)
5. {
6.     // TODO: move these typedefs somewhere more useful :P
7. #if (__cplusplus <= 199711L)
8.     typedef std::tr1::unordered_set<std::string> unordered_set;
9. #else
10.     typedef std::unordered_set<std::string> unordered_set; // don't use "using" syntax here to avoid additional checks for VS versions earlier than 2013
11. #endif
12.     if (strlen(token) > 199) // TODO: remove this limit from save game format?
13.         quit("!Game.DoOnceOnly: token length cannot be more than 200 chars");
14.     // TODO: REPLACE char** GameState::do_once_tokens with unordered_set* GameState::do_once_tokens
15.     //     NOTE: use a pointer to the unordered_set to preserve the size of the GameState struct (VS2008 reports sizeof(unordered_set) at 64)
16.     // TODO: REMOVE int GameState::num_do_once_tokens (now available as GameState::do_once_tokens->size())
17.     return play.do_once_tokens->insert(token).second; // all we need to know is whether insertion took place
18. }

GameState::num_do_once_tokens would probably be best left as an additional reserved space, since I know how touchy AGS is about struct layouts.

Is there any reason why anyone would object to this? Storing a pointer to the unordered_set isn't necessarily ideal, but it does preserve the existing layout and doesn't incur additional overhead as dereferencing was taking place anyway.

Game.DoOnceOnly likely isn't used as a speed-critical method, but this seems to me like a relatively simple optimization.

P.S. This would, of course, require other minor modifications, such as changing the method that writes the tokens to a save game, but iterating the unordered_set is extremely simple as well.

[Gurok]

No objections here. As you've mentioned, this is very similar to what we've been doing everywhere for the "remove limits" changes.

Have you checked the DoOnceOnly token format in save games? I don't have the code handy, but at a guess there's probably something silly like a 200 byte field for each token. I think leaving it as a TODO is valid. We should probably add the 199 char limit to the documentation though.

While you're there though... it's reporting that you can't have a token longer than 200 chars, but the test is for 199 chars. I appreciate that the null terminator means 200 chars are stored, but it might be friendlier to state the actual limit of 199 visible chars to users.

Really though, it all seems fine to me.

[Crimson Wizard]

Hi, please don't do "#if (__cplusplus <= 199711L)" in the local function code. Since the type is common (a set of strings) make a typedef in the global header instead.
You may see Common/util/string_types.h for the reference.

This is also because you would need to include different header for GCC.

(I wish we could do template typedefs, but that does not work in C++03)

Code: C++

1.     // TODO: REPLACE char** GameState::do_once_tokens with unordered_set* GameState::do_once_tokens
2.     //     NOTE: use a pointer to the unordered_set to preserve the size of the GameState struct (VS2008 reports sizeof(unordered_set) at 64)
3.     // TODO: REMOVE int GameState::num_do_once_tokens (now available as GameState::do_once_tokens->size())
4.     return play.do_once_tokens->insert(token).second; // all we need to know is whether insertion took place
5. }

GameState::num_do_once_tokens would probably be best left as an additional reserved space, since I know how touchy AGS is about struct layouts.

Is there any reason why anyone would object to this? Storing a pointer to the unordered_set isn't necessarily ideal, but it does preserve the existing layout and doesn't incur additional overhead as dereferencing was taking place anyway.

There is no problem in replacing this part of the GameState struct, because it's not referenced in script, nor exported to plugin API. Only upper part of the struct is. See my comments inside the struct like "up to here is referenced in the script "game." object". Therefore you do not need to use the "pointer trick" in this case.

The save game should not store any actual pointers (this was fixed long ago), it saves 0 always. It needs just to save the number of tokens, meaning the format won't change with this modification.


Regarding removing string limits, you may reference changes to the GUI name length:

Code: C++

1.     if (gui_version < kGuiVersion_340)
2.     {
3.         Name.WriteCount(out, GUIMAIN_NAME_LENGTH);
4.         OnClickHandler.WriteCount(out, GUIMAIN_EVENTHANDLER_LENGTH);
5.     }
6.     else
7.     {
8.         StrUtil::WriteString(Name, out);
9.         StrUtil::WriteString(OnClickHandler, out);
10.     }
11.  

Checking game data version should work for now. In the future, if the save format is replaced, the individual format number for Game State could be used.

[monkey0506]

Hi, please don't do "#if (__cplusplus <= 199711L)" in the local function code. Since the type is common (a set of strings) make a typedef in the global header instead.
You may see Common/util/string_types.h for the reference.

This is also because you would need to include different header for GCC.

(I wish we could do template typedefs, but that does not work in C++03)

I did put a comment that the conditional compilation shouldn't really exist inside the local function. What might make the most sense would be to add a conditional macro (in a header, of course) to select either std::tr1 or std depending on whether C++11 is supported. This would be sufficient to still use the actual templates in lieu of alias templates in C++03.

Code: C++

1.     // TODO: REPLACE char** GameState::do_once_tokens with unordered_set* GameState::do_once_tokens
2.     //     NOTE: use a pointer to the unordered_set to preserve the size of the GameState struct (VS2008 reports sizeof(unordered_set) at 64)
3.     // TODO: REMOVE int GameState::num_do_once_tokens (now available as GameState::do_once_tokens->size())
4.     return play.do_once_tokens->insert(token).second; // all we need to know is whether insertion took place
5. }

GameState::num_do_once_tokens would probably be best left as an additional reserved space, since I know how touchy AGS is about struct layouts.

Is there any reason why anyone would object to this? Storing a pointer to the unordered_set isn't necessarily ideal, but it does preserve the existing layout and doesn't incur additional overhead as dereferencing was taking place anyway.

There is no problem in replacing this part of the GameState struct, because it's not referenced in script, nor exported to plugin API. Only upper part of the struct is. See my comments inside the struct like "up to here is referenced in the script "game." object". Therefore you do not need to use the "pointer trick" in this case.

The save game should not store any actual pointers (this was fixed long ago), it saves 0 always. It needs just to save the number of tokens, meaning the format won't change with this modification.

I see, that's good to know.

Regarding removing string limits, you may reference changes to the GUI name length:

Code: C++

1.     if (gui_version < kGuiVersion_340)
2.     {
3.         Name.WriteCount(out, GUIMAIN_NAME_LENGTH);
4.         OnClickHandler.WriteCount(out, GUIMAIN_EVENTHANDLER_LENGTH);
5.     }
6.     else
7.     {
8.         StrUtil::WriteString(Name, out);
9.         StrUtil::WriteString(OnClickHandler, out);
10.     }
11.  

Checking game data version should work for now. In the future, if the save format is replaced, the individual format number for Game State could be used.

Thanks for the tip. I'll go ahead and make these changes then.

[Crimson Wizard]

I do not know how this story ended, but monkey0506 had never committed this change.

On other hand, I was considering replacing "play.do_once_tokens" with an unordered_set<String> during my work of modifying savegame format, but I encountered one issue which I did not want to solve for the sake of sticking to one task at a time.

The thing that bothered me is that DoOnceOnly gets a string as "const char*", and if we'd had do_once_tokens as a set of AGS::String (or std::string) objects, we would have to allocate a new temporary string every time just to do the check. That is probably not the slowest operation, but since we are talking about speed optimization here, my perfectionism kicked in.

The options here are:
1) Using std::unordered_set<const char*> for the time being; or unordered_set< shared_ptr<const char*> > to make things safer.
2) Writing custom comparison between const char* and String (?) for this set.
3) Otherwise we could perhaps do profiling to be certain that [using set + converting string type] works faster than iterating over array. I do not trust intuition in such case.
NOTE: const char* is coming from the script, replacing script strings with string class is doable, but far from trivial, and will likely require to abandon current plugin API..... which is why I don't suggest this here.