135 replies to this topic

[i30817]

It might be that the buffer that it uses to copy the string into to check is pre-allocated to a certain size, and that string needs a relocation. Then after the copy and comparison, the memory is freed and a new array with the default (inadequate) size is allocated.

No idea why it would only start manifesting in the middle of the game; unless there is something on baldur.bsc that stopped it from happening before.


The other alternative is that there is a memory leak in the process above, but i'd imagine that would eventually cause a crash from out of memory, not stuttering.

Other possibilities:
The hash function of the underlying hashmap (if any) is defective as soon as it exceeds a certain length - very unlikely.

There's a funky cache that gets invalidated.

You have enough string mappings that a combination of a "bad" hash based on the number of characters, and size of the dictionary/hashmap cause a lots of strings to map to a boundary slot. Say the hash is based on a sum of the chars, the hashmap has a current size 5000 (enough for all strings yet, the problem is not that it hasn't enough slots, but that the hashcode is not zooming on the right slot), after 23 characters all strings hashcodes > 5000, so they get all assigned to the last slot, and the hasmap algorithm degenerates into a linear search + string equality testing - i think this one is very likely.
The cause of this is that the hashcode is being used incorrectly, either truncating the result to fit on the array without modular arithmetic, or that the hascode is giving many strings the same slot.

Edited by i30817, 12 April 2012 - 06:49 PM.

[Suslik]

It might be that the buffer that it uses to copy the string into to check is pre-allocated to a certain size, and that string needs a relocation. Then after the copy and comparison, the memory is freed and a new array with the default (inadequate) size is allocated.

It may be even implemented inside STL code used by the engine, not in the engine code itself.

No idea why it would only start manifesting in the middle of the game;

I suppose it has to do something with variables stored in savegame file. Once certain amount of variables is reached, some pool may be resized in a wrong way or something like that. Needs investigation.

unless there is something on baldur.bsc that stopped it from happening before.

Baldur.bcs is irrelevant. The game stutters with savegame 2 and does not stutter with savegame 1, while both of them use the same test Baldur.bcs:

IF
        Global("123456789012345678901234","GLOBAL",5)
THEN
        RESPONSE #100
END

IF
        Global("123456789012345678901234","GLOBAL",5)
THEN
        RESPONSE #100
END

IF
        Global("123456789012345678901234","GLOBAL",5)
THEN
        RESPONSE #100
END

//about ~10000 lines of such copy-pasted code

There are no other blocks except for these. Apparently it is not a problem of some .bcs script. I think it's a bug in the executable and probably memory manager of the virtual machine it uses to run game scripts.

The hash function of the underlying hashmap (if any) is defective as soon as it exceeds a certain length - very unlikely.

I suppose the game uses STL structures such as std::map<std::string, T>/std::hash_map<std::string, T>. The first one does not require hash function and uses default operator < for std::string, while the second one probably uses some standard and reliable implementation of hash function.

I think it's not an error, but a case when the algorithm starts working ineffectively. Like some variable gets allocated on the heap instead of being cached in stack or something like that.

Edited by Suslik, 12 April 2012 - 06:48 PM.

[i30817]

Don't you'll wish IE was open source?


BTW, i edited the post above - i think the last idea is much more likely.

Edited by i30817, 12 April 2012 - 06:53 PM.

[i30817]

Hey, wait a minute. The string doesn't exist in the globals yet??

Because (in a "classical" hashmap) then it has to check all contiguous occupied slots around the hashcode slot for the string, to see if the mapping exists - to avoid hashcode collisions.

So the half a second pause is it checking near all the map (or all the map, if it's badly programmed), for a non-existant map on the mid-game globals map full of strings.

Strange that the size of the string has anything to do with it in that case though. It's a mystery.

[Suslik]

after 23 characters all strings hashcodes > 5000, so they get all assigned to the last slot, and the hasmap algorithm degenerates into a linear search

Well, I suppose no one truncates hashfunction's value to determine the number of buckets. Usually you do something like this:

int bucketNum = hash("some string") % buckectsCount;

Apparently you will get a lot of collisions with a small number of buckets and/or large hash values.

Don't you'll wish IE was open source?

Oh, it would be soo damn easier to mod it =(

Because (in a "classical" hashmap) then it has to check all contiguous occupied slots around the hashcode slot for the string, to see if the mapping exists - to avoid hashcode collisions.

Unfortunately, irrelevant. Setting the value to anything does not affect stuttering.

Edited by Suslik, 12 April 2012 - 06:59 PM.

[i30817]

after 23 characters all strings hashcodes > 5000, so they get all assigned to the last slot, and the hasmap algorithm degenerates into a linear search

Well, I suppose no one truncates hashfunction's value to determine the number of buckets. Usually you do something like this:

int bucketNum = hash("some string") % buckectsCount;

I know. That's why it would be stupid, though i can't think of another reason for the "magic 23".

Because (in a "classical" hashmap) then it has to check all contiguous occupied slots around the hashcode slot for the string, to see if the mapping exists - to avoid hashcode collisions.

Unfortunately, irrelevant. Setting the value to anything does not affect stuttering.

That new post was a observation that the pause would be "normal" if you were to check a string that doesn't exist in a huge fully occupied map without free slots.
Though it should have then happened to ALL non-existing strings, which makes no sense.

Maybe it does? And there aren't so many "non-existing strings on the map" anymore? That one on baldur.bcs could be one of the few that is on a global script and has no value in the globals yet, so it's constantly checking the whole globals map.
edit: but no, you tried with other values < 23 without a mapping and had no stutter right? And besides, hashmaps are normally coded to never let themselves get fully occupied for this very reason.


Stumped.

Edited by i30817, 12 April 2012 - 07:08 PM.

[Suslik]

Anyway. I think in order to solve the mystery there are 2 ways:
1) Try to reverse the stuttering via disasming the executable. It may prove troublesome, because I'm quite lame at this and it's rather difficult to make Asc64 reproduce the bug, because he has different set of mods than I do and my savegames will be screwed on his setup.
2) Try to analyze the two savegames and figure out the difference. Once it's done I can try to inject it into vanilla save and then Asc64 can easily reproduce it in vanilla and hopefully fix.

Edited by Suslik, 12 April 2012 - 07:09 PM.

[i30817]

I think you'll have trouble to do it in vanilla without stressing the globals (i really really hope it's a map and not a list) map.

Edit: then again, i suppose you can just use the same savegames in vanilla right? The map is full on unused values, should do no harm, as long a mods didn't change default bioware variables to "new" values. And even so, it should do no harm, because Asc64 won't play the game with the save, but try to debug the pauses.

Edited by i30817, 12 April 2012 - 07:21 PM.

[Suslik]

I have figured out that the bug is stored somewhere in BALDUR.GAM file of the savegame. If I inject baldur.gam from non-stuttering save to stuttering one, the game starts running normally. But if I export the savegame to vanilla, it refuses to load the game(freezes in the middle of loading process).

Shadow keeper cannot help here, since he shows only script-related values, but they are irrelevant. Is there any info on .gam file structure? I can try and parse it manually.

Edited by Suslik, 12 April 2012 - 07:29 PM.

[Sasha Al'Therin]

my game isn't set up the same as yours so I can't load the saves and expect the same results. At any rate scripts are not stored in the save file so if the culprit is the baldur.bcs then chances are no one else will see the problem with your saves.

however I can load them up in DLTCEP and do a side by side comparison.

Stutter vs Stutter free
1996 listed vars vs 1475 listed vars
71 joinable NPCs vs 67 joinable NPCs
99 personal effects on PC vs 93 personal effects on PC

with that info alone, looks to me like something was added between the two saves. # of party joinables doesn't change in the .GAM file unless you add more in via mod between sessions. Do you remember adding any new mods or adjusting any installed mods in any way? If so, you should try reversing such change...

[i30817]

Mmmm. What would happen if the hashcode overflowed into negative numbers?

-X % in C++ doesn't launch a exception or anything does it? Or result on a negative number?

ISO/IEC 14882:2003 : Programming languages -- C++. 5.6.4: ISO, IEC. 2003. "the binary % operator yields the remainder from the division of the first expression by the second. .... If both operands are nonnegative then the remainder is nonnegative; if not, the sign of the remainder is implementation-defined".

herp.

[Suslik]

with that info alone, looks to me like something was added between the two saves

I did add a debugging mod to print which blocks are executed according to this thread(during the investigation): http://www.shsforums...ing-stuttering/ But both saves are made with this mod and one of them apparently does not stutter.

The only different thing between these two saves is about 1 day(real day i mean) of gameplay. I did not install/remove any mods - it's the same playthrough.

my game isn't set up the same as yours so I can't load the saves and expect the same results

But can you load these saves or do you receive some error? If you can load them, I can send you the test Baldur.bcs and even though all your string entries will be messed, you should be able to check if it stutters or not.

-X % in C++ doesn't launch a exception or anything does it? Or result on a negative number?

I highly doubt that it would not crash the whole thing and that it only happens with variables longer than 23 letters lol.

Edited by Suslik, 12 April 2012 - 07:41 PM.

[i30817]

It wouldn't explain the stutter, but it would explain the +23 thing. You even have a case (all 'a', which is 62 in ascii, in contrast with the digits you used in the others, which map to the same number) that stutters with 23! So i think the hashcode is failing somehow.

If it's a overflow into negative numbers ("somehow") affecting the stutter, you should be able to test it by doubling again to see if you can get it positive again.

if there's a case where 24 chars stutter and 48-49 don't...

Edited by i30817, 12 April 2012 - 07:54 PM.

[Suslik]

i30817
c'mon. it starts to sound like magic :/ hashmap is a basic mechanism which in the worst degenerated case works slow, O(n^2), I highly doubt that it can fail on a simple case of a string longer than 24 characters. specially for you I have tested names with length of 42 and 50 and both of those stutter.

I have tested the two saves in BWP 9.4 standard. Just as expected - stuttering savegame stutters while stuttering-free does not, regardless of BWP version. Damn, why can't I load these saves in vanilla?

Edited by Suslik, 12 April 2012 - 08:01 PM.

[i30817]

i30817
c'mon. it starts to sound like magic :/

http://catb.org/jarg...agic-story.html

Maybe it's the area files inside the save that prevent you loading it on the base game?

Edited by i30817, 12 April 2012 - 08:11 PM.

[Sasha Al'Therin]

But can you load these saves or do you receive some error?

No See this:

Maybe it's the area files inside the save that prevent you loading it on the base game?

Since all saves store the data from areas which you have visited, if those areas do not exist on the game being used to load said saves, they will not load as there is no data to support the stored data.

Try to replicate the issue in unmodded BG2 or base install BGT (i.e. BG2Fixpack followed by BGT) if you can reproduce it by using long variable names, then you've got yourself a case.

At any rate the character field is 32 characters long for variables and truncated further to 18 characters for scripting name variables on creatures due to the SPRITE_IS_DEAD qualifier prepended to a snv (or dv as it is sometimes called).

Global("This_cant_any_be_longer_than_32_","GLOBAL",1)
While that is valid and typically can be used without any issues, it could be possible that multiple variables longer than 18 will begin to have issues. Curious to know how many exactly of a specific variable name length you have to had before the stutter occurs.

Also if one save game does not stutter and yet the other does and you are adamant that you changed nothing between the two other than having played the game for a bit, there may then be something else mod related which is causing the stutter that gets loaded up in the one game but not the other. The fact that it goes away when you delete baldur.bcs may simply be that nothing is running which interferes with the mod added thing.

[Suslik]

Maybe it's the area files inside the save that prevent you loading it on the base game?

How can I inject some info from my current save to vanilla save? Maybe somehow erase all cached areas/items? I have never messed with savefiles, any ideas are much appreciated.

Also if one save game does not stutter and yet the other does and you are adamant that you changed nothing between the two other than having played the game for a bit, there may then be something else mod related which is causing the stutter that gets loaded up in the one game but not the other. The fact that it goes away when you delete baldur.bcs may simply be that nothing is running which interferes with the mod added thing.

Look, it cannot be mod or gamescript related. It is my synthetic baldur.bcs which stutters just the same way as my normal game does. And apparently it stutters in one savegame and does not stutter in another. Absolutely the same checks are executed in both games(I have made the test badlur.bcs this way to avoid anything else from interfering) and one somehow works far slower than the other.

I think this stuttering mechanism is somehow related to cached variables/areas/items/idontknowwhat inside the baldur.gam file.

Try to replicate the issue in unmodded BG2 or base install BGT (i.e. BG2Fixpack followed by BGT) if you can reproduce it by using long variable names, then you've got yourself a case.

It's not that easy. Normally my test baldur.bcs with tons of GetGlobal("a_really_long_value_with_more_than_24_letters", "GLOBAL") does NOT lag. It only started lagging after a certain point in current playthrough, and unfortunately I do not know how to export this state to vanilla game in order to reproduce it.

Curious to know how many exactly of a specific variable name length you have to had before the stutter occurs.

Until the game goes to that stuttering state any amount of such variables can be used without introducing stuttering. But when the game starts to stutter, only one variable(replicated about 500 times) will stutter the game a lot. Again, until a certain point of gameplay the game does not stutter regardless of what variables you are using.

Edited by Suslik, 13 April 2012 - 05:10 AM.

[Suslik]

Update: I have found two savegames with difference only about one hour of gameplay. One game stutters and the other does not. They are called "stutter test 2" and "stutter free test 2", and can be found by the same link http://dl.dropbox.co... test saves.zip

Sasha Al'Therin, you seem to know something about structure of savegames, can you please take a look into those?

Edited by Suslik, 13 April 2012 - 05:23 AM.

[Sasha Al'Therin]

If it is a CERTAIN POINT in gameplay then that point needs to be looked at. As apparently your 'stutter-free' save has not reached that point and your 'stutter' save has. Again I will point out that it could be mod related. You say it is not, BUT there are other scripts and other processes which run concurrently to baldur.bcs. by deleting your baldur.bcs you free up any lag created by running it and allow other mod content to run or not run as it sees fit.

You've yet to state that you've humored me and as to the effects that happen:

1) Turn sounds off one by one, see if the stutter goes away.
2) Turn party AI off, see if the stutter goes away.
3) Change areas, see if the stutter goes away.

You seem so hell bent on it being in baldur.bcs, that it can't be anything else. I pointed out to you that your saves were quite different. Naturally one may stutter and one may not. For there to be real proof both saves need to be identical save for the long variable names.

How can I inject some info from my current save to vanilla save?

Start a brand new game and replace baldur.bcs with your crap load of repeated long variable name blocks. If you reach a greater amount of blocks and it does not stutter, then again the issue is in relation to SOMETHING ELSE in your game. That something else is most likely mod added.

You seem to know programing pretty well, ever notice a compiler that reports an error on one line but nothing is wrong with it. The true problem lies a few lines above where a single character such as a bracket or quote was missing. This could very well be similar. baldur.bcs is having a problem because something else is interfering with it.

[Suslik]

You've yet to state that you've humored me and as to the effects that happen:

1) Turn sounds off one by one, see if the stutter goes away.
2) Turn party AI off, see if the stutter goes away.
3) Change areas, see if the stutter goes away.

You seem so hell bent on it being in baldur.bcs, that it can't be anything else. I pointed out to you that your saves were quite different. Naturally one may stutter and one may not. For there to be real proof both saves need to be identical save for the long variable names.

Ok. Why am I about 99% sure that it is my baldur.bcs with crapload of long GetGlobal() stutters and not anything else. I did an experiment:

- with empty baldur.bcs none of savegames stutter. so if nothing useful is done in baldur.bcs, no sounds, no other mods, no dplayer3.bcs and no character scripts cause stuttering.
- then if I add test code into baldur.bcs with GetGlobal readings, stuttering game starts stuttering. Apparenly all the other mod-related scripts in dplayer3.bcs, charname.bcs and other will go exactly the same way as they did with an empty badlur.bcs, right?

by deleting your baldur.bcs you free up any lag created by running it and allow other mod content to run or not run as it sees fit.

why is that? every script that is supposed to be executed every second will be executed every second regardless of how much my baldur.bcs lags.

You seem to know programing pretty well, ever notice a compiler that reports an error on one line but nothing is wrong with it. The true problem lies a few lines above where a single character such as a bracket or quote was missing. This could very well be similar. baldur.bcs is having a problem because something else is interfering with it.

I see your point. But I did so much tests already and they all fit perfectly well to the fact that it is GetGlobal's get stuttering, not any sounds/AI scripts/etc. There are no contradictions with this hypothesis. There's only one question left - under which circumstances do these GetGlobal's start stuttering.

Edited by Suslik, 13 April 2012 - 05:38 AM.