less precise sorting in range manager

[real_tabasco_sauce]

13 minutes ago, Stan` said:

So... It's worse than without the patch?

Yeah, i think slightly worse, but its hard to say. It would be great if @wraitii could profile it. I modified EntityDistanceOrdering, which is used by all the different range queries, so its possible this version could be used in less locations.

Also, I do whole division after finding the square root:

u32 r2 = isqrtEst64(d2,P)/(100000*P);

but it might be faster to find the sqrt after whole number division.

[Stan`]

In a non visual replay iirc isqrt takes about 1% of a match.

[real_tabasco_sauce]

Wow thats huge. I tried replacing the isqrt64() in FixedVector2D.Length() with my isqrtEst64() with P=1 and got teleporting units and a game crash.

In theory, the new sqrt with P=1 should be exactly the same as isqrt(), so maybe Ill need to compare the two to figure out what happened above.

Edited Tuesday at 18:45 by real_tabasco_sauce

[Stan`]

32 minutes ago, real_tabasco_sauce said:

Wow thats huge. I tried replacing the isqrt64() in FixedVector2D.Length() with my isqrtEst64() with P=1 and got teleporting units and a game crash.

In theory, the new sqrt with P=1 should be exactly the same as isqrt(), so maybe Ill need to compare the two to figure out what happened above.

A good question one should ask is whether all the calls to that function are justified, whether they can be cached or batched.

[real_tabasco_sauce]

Ok, so I was checking the isqrtEst64 against isqrt(), and they are exactly the same when P = 0.

However, because I am using SLD2's "SDL_MostSignificantBitIndex32(n)" to get log2, large integers overflow.

u64 sqrt_lo(const u32 n) noexcept
{
	u32 log2floor = SDL_MostSignificantBitIndex32(n);
	return (n != 0) << (log2floor >> 1);
}

u32 isqrtEst64(u64 n, u8 P = 0)
{
	u32 est = sqrt_lo((u32)n);
	u32 b = (u32)n;
  ...

The nice thing is the larger values don't occur in fights, I guess they happen in map generation and pathing, probably a lot of other things. As far as I can tell, the patch is working, but I am sure there are more improvements possible.

So @Stan` I would need to come up with a 64 bit equivalent to SDL_MostSignificantBitIndex32(n) in order to see if this sqrt approach could be faster than the current isqrt().

Edited Thursday at 19:16 by real_tabasco_sauce

[Stan`]

int reverseMostSignificantBit(uint64_t n) {
    if (n == 0) return -1; // If n is 0, there is no significant bit set.
    
    int msb = 63; // Start with the highest bit position (63 for 64-bit numbers)
    uint64_t mask = 1ULL << 63; // Initialize the mask to check the highest bit
    
    while (mask > 0 && !(n & mask)) {
        msb--;
        mask >>= 1; // Move the mask to the next lower bit
    }
    
    return msb;
}

That's a naive way for that function. I must say I'm not yet convinced of your approach but we'll see.

Another simpler version depending on the number size, might make a speed difference.
 

int mostSignificantBit(uint64_t n) {
    if (n == 0) return -1; // If n is 0, there is no significant bit set.
    
    int msb = 0;
    while (n >>= 1) {
        msb++;
    }
    return msb;
}

 

[real_tabasco_sauce]

ok, I got a 64 big equivalent working, and I tested every isqrt() call against isqrtEst64(), and not once was there a difference. Do you think I should just wing it and replace the old isqrt()?

[Stan`]

Well is it faster ?

[real_tabasco_sauce]

35 minutes ago, Stan` said:

Well is it faster ?

After a couple of combat demo huges, it seemed a little faster, but that's just anecdotal. Also, i don't know if my build was making use of the builtins, so it may be better or worse than what I experienced for some players.

I uploaded the latest version (with the isqrt64() replacement). 

Edited Friday at 18:37 by real_tabasco_sauce

[real_tabasco_sauce]

ok, well the patch is pretty much done and working: https://code.wildfiregames.com/D5282

if anyone can apply it (and build) to test on their system that would be great!

[guerringuerrin]

@real_tabasco_sauceI'd be happy to test it, but I'd need some guidance on how to apply the patch. 

[real_tabasco_sauce]

Ok so the way I do it is this:

1. in phabricator(https://code.wildfiregames.com/D5282), click "Download Raw Diff", this will open a plain text file in your browser.
2. Copy the contents of the file
3. navigate to your SVN directory
4. Paste the contents into a new file with the extension '.diff'
5. type 'svn patch ABC.diff'

now at this point, some files should print to console with 'U' for updated. bigger patches might have conflicts, but that shouldn't be the case here. Since this patch modifies the engine, you will need to also build the game: https://trac.wildfiregames.com/wiki/BuildInstructions

Edited 21 hours ago by real_tabasco_sauce