Optimized… in Assembler

OK, now for the fanatics as always: The same thing I just posted, but in assembler:

BitReverse PROC
PUSH r13

MOV rax, rcx
MOV r13, rcx
SHR rax, 1
AND rax, 0x5555555555555555
AND r13, 0x5555555555555555
SHL r13, 1
OR rax, r13

MOV r13, rax
SHR rax, 2
AND rax, 0x3333333333333333
AND r13, 0x3333333333333333
SHL r13, 2
OR rax, r13

MOV r13, rax
SHR rax, 4
AND rax, 0x0F0F0F0F0F0F0F0F
AND r13, 0x0F0F0F0F0F0F0F0F
SHL r13, 4
OR rax, r13

MOV r13, rax
SHR rax, 8
AND rax, 0x00FF00FF00FF00FF
AND r13, 0x00FF00FF00FF00FF
SHL r13, 8
OR rax, r13

MOV r13, rax
SHR rax, 16
AND rax, 0x0000FFFF0000FFFF
AND r13, 0x0000FFFF0000FFFF
SHL r13, 16
OR rax, r13

MOV r13, rax
SHR rax, 32
SHL r13, 32
OR rax, r13

POP r13

ret

BitReverse ENDP

Optimizing the BitReverse

Well well well, seems finally a way emerged to do the reversing without the need of a loop. And here is the trick:

Figure this simple starting value (16 bit for demo, works the same with 64 of course):
1010000010100000
Now let’s do a little bit math:
1) We just flip all odd and even bits using a 0101010101010101 mask. For this we use the original value twice, one time shifted left by 1 bit, one time shifted right, then ANDed with the mask and back ORed together. Here is the code:
i=((i>>1) & 0x5555) | ((i & 0x5555)<<1);
What does that do? Let’s break it up:
i>>1 translates to: 0101000001010000. Now do the AND 0x5555:
0101000001010000
0101010101010101
result:
0101000001010000.
The original ANDed with 0x5555 means:
1010000010100000
0101010101010101
result:
0000000000000000
Now OR those together and you get 0101000001010000

2) Now we use 0011001100110011 as bit mask and do it again, basically flipping pairs:
i=((i>>2) & 0x3333) | ((i & 0x3333)<<2)
First half:
0101000001010000 >>2 –> 0001010000010100
AND 0011001100110011
result: 0001000000010000
Second half:
0101000001010000 AND
0011001100110011
result: 0001000000010000 << 2 : 0100000001000000
Now OR those:
0001000000010000
0100000001000000
result: 0101000001010000

3) Now we swap nibbles, but I think you got the point…
0101000001010000 –> 0000010100000101

4) Last we swap the bytes. (Which in this case results in no change.)

Voila, the bits are flipped…

Here is the sample code for 64 bit in C#:

[SqlFunction]
public static Int64 Reverse(Int64 inVal)
{
    ulong Result=(ulong) inVal;
    // odd and even
    Result=((Result>>1)& 0x5555555555555555)|((Result & 0x5555555555555555)<<1);
    // pairs
    Result=((Result>>2)& 0x3333333333333333)|((Result & 0x3333333333333333)<<2);
    // nibbles
    Result=((Result>>4)& 0x0F0F0F0F0F0F0F0F)|((Result & 0x0F0F0F0F0F0F0F0F)<<4);
    // bytes
    Result=((Result>>8)& 0x00FF00FF00FF00FF)|((Result & 0x00FF00FF00FF00FF)<<8);
    // words
    Result=((Result>>16)& 0x0000FFFF0000FFFF)|((Result & 0x0000FFFF0000FFFF)<<16);
    // double words
    Result=(Result>>32)|(Result<<32);

    return (Int64) Result;
}

One thing: If you (like me) want to flip only 63 bits (to keep the value positive) just add Result=Result<<1; before the even/odd flip.

Thanks very much to the anonymous poster that brought up the idea.

MutliSubnetFailover – the DNS conundrum

I love new technology and I love new ideas, but sometimes the coolest of those are somewhat not thought through… When Microsoft announced the support for multisubnet clustering in SQL 2012 I was cheerful, as this is a feature that can come in really handy in time like these. Unfortunately in the real world this new feature soon proved to be … let’s say … improvable.

Here’s the deal: When you have a virtual network name (VNN) in a cluster with multiple IP addresses behind it in the end what that does is automatically reset DNS entries whenever you failover the group. Now as all of you know (and if you don’t know it’s still a fact unfortunately…) client computers have this nasty thing that’s called “DNS resolver cache”, which basically means that names that have already been resolved to IP addresses will be cached locally and not sent to the DNS server again for a while. (That while is called the “Time to Live”, or TTL for short.) VERY good idea in normal life, otherwise DNS Servers would have a real problem and every request would be WAY slow… Unfortunately… VERY bad idea for failover scenarios like ours with the DB, especially if you require real high availability…

OK, now, Microsoft is not THAT stupid… in fact they have quite smart people there and those people thought about this problem too. What they did to tackle this was quite simple: Make the client driver aware of the problem so it can solve it. The way they did this was… well… Interesting at best… They changed the behavior of the VNN so it would always register all IPs in DNS, not only the active one, (ok, this was not a real change, cluster service had this feature for a while now, they just use it…) and build a change into the client to get all those IPs and automatically connect and reconnect to the active one.

Nice idea in theory… The problem starts when you begin using applications that are not aware of that idea. Why? Because what happens by default when you have multiple IPs in DNS is that the client fetches a random one (OK, not really random, but it doesn’t matter for now…) and places that one in his cache. If that one is the one that is currently inactive… Well… Let’s call it a bad day… You will just not get a connection open, and the server will not fetch a new IP because the resolver cache already has one… So… Tough luck…

OK… Enough with that… So how do you overcome this problem? Well, unfortunately there is no really good way to do it… (Unless of course all your applications can be made aware of the situation by using the latest drivers…) Here is what I would do for now as a next best thing to a solution:

1. Stop the DNS behavior of the VNN, let it run as it would have normally. Unfortunately you can’t change this in the UI, only via commandline: cluster.exe RES <ResourceName> /PRIV RegisterAllProvidersIP=0
2. Reduce the TTL of that DNS entry to whatever is the longest you can possibly wait for a failover. I chose 15 seconds for that, but feel free to go your own way. Luckily this setting can be changed in the DNS management UI.
3. Still keep the MultiSubnetFailover=True parameter in the apps that support it. It doesn’t really help, but maybe you reach the point at some time where you have a homogenous system again and can use that new pattern.

There is an alternative way too that might even be better than this one. But I would strictly only recommend this if your system is rather small. (In numbers of DBs…) You could leave the SQL listener as it is and connect your MutliSubnet aware applications there. Then add a second VNN to the group that is set with minimal TTL and no RegisterAllProvidersIP flag to connect your legacy apps to. This setup will give you maximum availability and flexibility, but it requires extra work and extra IP addresses…

BitReverse again

Just to satisfy the high performance fanatics: Below you find the most efficient reverser algorithm I could write so far.Unfortunately getting this code into SQL Server is not as simple as it might look. ODS (the extended stored procedure API) seems to have more overhead than the CLR and CLR interop also generates more overhead than you can save. If anybody has good ideas on how I can get this efficiently in, please give me a ping.

BitReverse PROC
PUSH r13

XOR rax, rax
MOV r13, rcx
MOV rcx, 63
JumpLabel:
SHR r13,1
RCL rax,1
LOOP JumpLabel
POP r13

ret

BitReverse ENDP

When sp_ doesn’t mean “stored procedure”

For some people in the community this seems to be very common knowledge. Well, if it’s so then shame on me, because I didn’t know…

I have been asked some times how those special system stored procs like sp_help work. Those sprocs that only exist in master database, but still you can call them from every DB you are in. So far I thought this was something special, internal, of SQL Server… Well, wrong…

The trick is easy: Whatever object you create in master database that is called sp_<something> you can automatically use in every DB on that server. Because in this case sp_ doesn’t mean “stored procedure” but it means “special”…

Thanks at this point to Kelan Delaney who brought this up at a presentation today…

The day Sequences saved the world

In my last post I brought up the idea of reverse indexes and how those could save you from latch contentions.Well, after another day of hard work it turns out that the new Sequence feature in SQL Denali really is a kind of universal life saver for high load OLTP applications… I don’t know how many sequences we did already to get rid of latch contention and last page inserts, but I can tell you, it were quite a few…

There are two things I have to add though regarding my last post:

First… If you run sequences in really high load environments you have to use the CACHE feature. In the case of a server crash this might leave you with gaps in your sequence, but if you don’t use the Cache you will get locking issues on the sequence once you hit somewhere around 10.000 Fetch next statements per second.

And second… While my T-SQL bit reverser works perfectly fine it is sort of CPU intensive… Our 80-core server burnt about 1% CPU per 1000 rows inserted, with more than half of that going into the bit reverser. I did a lot of tests following this finding, and it almost hurts me to say that, but in this one case SQL CLR really is the best solution you can have… Using the CLR function instead of the T-SQL function we are almost down to nothing for the bit reverse.

Oh, and here is the code of the CLR function: (If anyone wants the compiled DLL or the complete solution please ping me and I’ll mail it to you.)

[SqlFunction]
public static Int64 Reverse(Int64 inVal)
{
    ulong Result = 0;
    ulong Input = (ulong)inVal;
    int i;
    for (i = 0; i < 63; i++) // 64 bits...
    {
        Result <<= 1; // Shift result by one digit
        if ((Input & 1) == 1) // If lowest bit of input is 1 add one to result
            Result++;
        Input >>= 1; // Now shift the input so that the next bit is lowest
    }
    return (Int64) Result;
}

Bit reversion

This might seem to be something you never need in SQL Server, but maybe you do and just never knew, so hear me out:
The problem started with a typical scenario for logging tables and even more with some OLTP tables that are heavily inserted: You have an identity column as your primary key (because GUIDs are taking too much time, or you just want bigints or whatever…) and due to the latch contention on the last index page you just can’t get more inserts than 10.000 a second. (OK, that might be enough for almost everyone… But maybe you are not almost everyone?) So what to do? The idea is called “Reverse index”… (Some other DB systems have those out of the box, SQL doesn’t… Doesn’t matter, we can build one…) the basic idea behind it is that you do a binary flip of the increasing number. How does this help? Well, look at the values you get: (tinyint as a sample…)

Identity value	Binary	Reverse	New value
1	00000001	10000000	128
2	00000010	01000000	64
3	00000011	11000000	172
4	00000100	00100000	32
5	00000101	10100000	160
6	00000110	01100000	96

You see how the values keep jumping? Now there is no latch contention anymore on the PK index…
OK, now how do you accomplish this?
First you need to get rid of the identity. Leave the PK without default value, or build your default with what comes next.
Second we need to get a new unique number. Let us all bow before SQL Server Denali, because it comes bearing gifts for us… The magic word is called SEQUENCE. and it is simple:
CREATE SEQUENCE <SomeSequenceName> START WITH 1 INCREMENT BY 1
Now you get the next value calling:
SET @Variable= NEXT VALUE FOR <SomeSequenceName>
Now all you need to do is the inversion… And here is how that is done: (The code works for Bigint…)
CREATE FUNCTION BitReverse
(
    @Input bigint
)
RETURNS bigint
AS
BEGIN
    DECLARE @WorkValue bigint=@Input
    DECLARE @Result bigint=0;
    DECLARE @Counter int=0;
    WHILE @Counter<63
    BEGIN
        SET @Result=@Result*2
        IF (@WorkValue&1)=1
        BEGIN
            SET @Result=@Result+1
            SET @WorkValue=@WorkValue-1
        END
        SET @WorkValue=@WorkValue/2
        SET @Counter=@Counter+1
    END
   
    RETURN @Result
   
END
And now you can glue this together… If you want a default value it might be easiest to get rid of the input Parameter for the BitReverse and query the sequence in the function itself, but this is up to you.