Coding style question

[Nick]

Q: In C#, what would you prefer?

byte b = 123;
b = (byte) Convert.ToInt32(b) >> 1;

or:

byte b = 123;
b = b / 2;

They should compile to the exact same thing. Replacing division by a constant power-of-two with a shift right is trivial for any optimizing compiler.

So I'd prefer the latter if what you're trying to do is just divide. The other case would be when it's important to make it clear that you're doing a shift, for example when you're decoding some binary format.

 

[Frank]

They should compile to the exact same thing. Replacing division by a constant power-of-two with a shift right is trivial for any optimizing compiler.

So I'd prefer the latter if what you're trying to do is just divide. The other case would be when it's important to make it clear that you're doing a shift, for example when you're decoding some binary format.

I don't know for sure, but I think the second example might be converted into a double, as that is the preferred type for divisions. In either case, the byte is converted at least twice. So doing a shift probably isn't going to be faster. But I use the first when doing something binary, as you said.

 

[Nick]

I don't know for sure, but I think the second example might be converted into a double, as that is the preferred type for divisions. In either case, the byte is converted at least twice. So doing a shift probably isn't going to be faster. But I use the first when doing something binary, as you said.

There's absolutely no conversion involved. Bytes are also stored in 32-bit registers. It's only a semantic change int the language. The C# JIT-compiler is practically as good as the C++ compiler so I have little doubt that all versions translate to one shift right instruction, nothing more.

I can highly recommend a book like Modern Compiler Implementation in C. Worth every cent. Even if you just glance through it, it clearly illustrates how a modern compiler works. Learning assembly and looking at disassembled C/C++ code during debugging is also a great start.

 

[Frank]

There's absolutely no conversion involved. Bytes are also stored in 32-bit registers. It's only a semantic change int the language. The C# JIT-compiler is practically as good as the C++ compiler so I have little doubt that all versions translate to one shift right instruction, nothing more.

I can highly recommend a book like Modern Compiler Implementation in C. Worth every cent. Even if you just glance through it, it clearly illustrates how a modern compiler works. Learning assembly and looking at disassembled C/C++ code during debugging is also a great start.

If that was true, why do I have to convert my byte into a 32-bit int to get it shifted?

byte b = 123;
b = b >> 1;

will result in a compiler error, as the only type allowed for ("complex" ???) integer operations is the Int32. As the double is the only (preferred?) one for floating-point operations. So, I'm pretty sure the .NET runtime converts *ALL* types into the required one for the operation before performing it. And that's why you need the explicit cast as well.

 

[ERP]

If that was true, why do I have to convert my byte into a 32-bit int to get it shifted?

byte b = 123;
b = b >> 1;

will result in a compiler error, as the only type allowed for ("complex" ???) integer operations is the Int32. As the double is the only (preferred?) one for floating-point operations. So, I'm pretty sure the .NET runtime converts *ALL* types into the required one for the operation before performing it. And that's why you need the explicit cast as well.

I'd be really surprised if the .Net runtime didn't support integer divides.

 

[Simon F]

They should compile to the exact same thing. Replacing division by a constant power-of-two with a shift right is trivial for any optimizing compiler.

Provided the value is unsigned.

 

[Frank]

I'd be really surprised if the .Net runtime didn't support integer divides.

Yes, it would be possible that more complex but common operations are supported, and the basic, but less common ones aren't. It's quite possible that I have to write "b / 2" to actually perform that shift operation, while "b >> 1" uses two conversions and a division instead.

Coding style is determined by the preferences of the platform, not the user? And efficiency is limited by the platform as well?

 

[Nick]

If that was true, why do I have to convert my byte into a 32-bit int to get it shifted?

byte b = 123;
b = b >> 1;

will result in a compiler error, as the only type allowed for ("complex" ???) integer operations is the Int32. As the double is the only (preferred?) one for floating-point operations. So, I'm pretty sure the .NET runtime converts *ALL* types into the required one for the operation before performing it. And that's why you need the explicit cast as well.

Ok, I checked this, and apparently shift operations are only defined for int, uint, long and ulong (32/64-bit). A possible explanation for this is that the MSIL bytecodes C# gets compiled into only support these types for code compactness. It might also make it easier to support it on architectures that don't have 8-bit or 16-bit shifts.

Anyway, shifting a byte is easy. It will be converted implicitely to int, so all you have to do is cast it back to a byte:

byte b = 123;
b = (byte)(b >> 1);

I'm certain the JIT-compiled x86 code won't contain any kind of conversion instructions.

I must admit it's strange though. I don't see a clear reason why they would have this limitation. Even without MSIL support they could easily allow byte shifts in the language and do the cast for you fully transparently. I think.

 

[Nick]

I read some discussions about the topic and it looks like they just want to encourage us to work with 32-bit (and 64-bit) variables all the time. In fact all C# operations are 32/64-bit (yes, dividing a byte by 2 and assigning the result to a byte doesn't compile)! So they expect we write code like this:

int i = array[123];     // Read a byte from memory

i = i >> 1;
i = i / 2;

array[321] = (byte)i;   // Write back to memory

32-bit arithmetic is most optimized on modern architectures anyway. So just let the byte be promoted to int automatically whenever you perform arithmetic operations on them. Only when you have to write it back to a byte you need to cast explicitely. Supposedly this is also less bug prone because ints don't overflow as easily as a byte.

Anyway, style wise, I'd just use shifts when you need to access bits, and use division when you want to divide the actual value. Using shifts for dividing a value is confusing and not faster, and using division to get to some bits is equally confusing. So just be explicit. Simple as that.

 

[Humus]

I looked at your framework source Humus, and you are rather consistent with the tabs, following the rule I see as OK. But there's still places were you indent with just spaces.

I'm very strict with that, but unfortunately there's a bug in VC6 and VC2003 that sometimes insert spaces even if you have it set to use tabs. In 99% of the time it's because of this. I occasionally hit Ctrl+R,Ctrl+W to check that it didn't insert any spaces for me, but of course I don't do this all the time so there will be some that slips through. You can reproduce the bug by starting with for instance this code:

for (int i = 0; i < 256; i++){
[COLOR=red]--->[/COLOR]for (int j = 0; j < 256; j++){
[COLOR=red]--->[/COLOR]}
}

Go to first line and hit Enter. You get this:

for (int i = 0; i < 256; i++){
    I <--- Cursor here, no spaces or tabs visible on this line yet.
[COLOR=red]--->[/COLOR]for (int j = 0; j < 256; j++){
[COLOR=red]--->[/COLOR]}
}

Now press delete twice to bring the previous line up and delete the tab. You get this:

for (int i = 0; i < 256; i++){
[COLOR=red]....[/COLOR]for (int j = 0; j < 256; j++){
[COLOR=red]--->[/COLOR]}
}

It appears this has been fixed in VC2005 though.

And you've kind of circumvented the problem in multi line function calls by never doing any, resulting in lines with sometimes >200 characters.

Well, I prefer long lines over wrapped lines. And you fit quite a lot on 1600 pixel, or 1920 as I have on my laptop. I do wrap some extremely long lines though, or simply split it into multiple statements if possible.

 

[Simon F]

Using shifts for dividing a value is confusing and not faster,

That maybe the case on the largest/most expensive CPUs, but divide often takes multiple clock cycles on more common devices.

Well, I prefer long lines over wrapped lines. And you fit quite a lot on 1600 pixel, or 1920 as I have on my laptop. I do wrap some extremely long lines though, or simply split it into multiple statements if possible.

What do you do when you print out your code?

 

[K.I.L.E.R]

I wish I had your knowledge.
You're my new hero, your the reason I'm going to university. Just so I can be like you.

I read some discussions about the topic and it looks like they just want to encourage us to work with 32-bit (and 64-bit) variables all the time. In fact all C# operations are 32/64-bit (yes, dividing a byte by 2 and assigning the result to a byte doesn't compile)! So they expect we write code like this:

int i = array[123];     // Read a byte from memory

i = i >> 1;
i = i / 2;

array[321] = (byte)i;   // Write back to memory

32-bit arithmetic is most optimized on modern architectures anyway. So just let the byte be promoted to int automatically whenever you perform arithmetic operations on them. Only when you have to write it back to a byte you need to cast explicitely. Supposedly this is also less bug prone because ints don't overflow as easily as a byte.

Anyway, style wise, I'd just use shifts when you need to access bits, and use division when you want to divide the actual value. Using shifts for dividing a value is confusing and not faster, and using division to get to some bits is equally confusing. So just be explicit. Simple as that.

Simon: What do you mean by common devices?
Are you refering to all desktop CPUs?

 

[Simon F]

Simon: What do you mean by common devices?
Are you refering to all desktop CPUs?

What I mean is not all CPUs are the latest and greatest x86. Older varieties, for example, and other chips are unlikely to have a single cycle (throughput) divider unit because that would be a big chunk of silicon. A shifter, OTOH, is relatively cheap.

 

[DemoCoder]

Ah, but there were CPUs that didn't have a barrel shifter unit too, and either looped back for higher shifts, or the compilers generated code that used multiple ror/lsr/rol/etc instructions. In those cases, a mask and table approach was often faster. (you have to go WAY back tho)

 

[Frank]

What I mean is not all CPUs are the latest and greatest x86. Older varieties, for example, and other chips are unlikely to have a single cycle (throughput) divider unit because that would be a big chunk of silicon. A shifter, OTOH, is relatively cheap.

Yes, and the .NET platform is what you're supposed to use on handhelds (Windows CE) as well. Who haven't got as much memory either.

 

[Simon F]

Ah, but there were CPUs that didn't have a barrel shifter unit too, and either looped back for higher shifts,

Absolutely. I used to program the transputer which had a instruction that took one cycle per shift. Unfortunately, it didn't mask out the upper bits so if you did ...

X := MaxInt;
....
y := y >> X;

...it would lock the processor up for around 100 seconds!!!

 

[Simon F]

That maybe the case on the largest/most expensive CPUs, but divide often takes multiple clock cycles on more common devices.


What do you do when you print out your code?

Actually I take that back.
It also applies to modern CPUs :smile:
On a fairly modern linux box, I just tried comparing (arbitrary) shifts against the equivalent divide and the shift was only around 10x faster.

 

[Nick]

That maybe the case on the largest/most expensive CPUs, but divide often takes multiple clock cycles on more common devices.

What I meant is that division by a constant power-of-two will get optimized by a shift anyway. That's the C# compiler's responsability. So style-wise it's always best to be explicit about what operation you want.

 

[Simon F]

What I meant is that division by a constant power-of-two will get optimized by a shift anyway. That's the C# compiler's responsability. So style-wise it's always best to be explicit about what operation you want.

It can ONLY do that if your dividend is unsigned.

If you are really worried about style/readability, put a macro/inline func around it to emphasise it.

 

[Nick]

Ah, but there were CPUs that didn't have a barrel shifter unit too, and either looped back for higher shifts, or the compilers generated code that used multiple ror/lsr/rol/etc instructions. In those cases, a mask and table approach was often faster. (you have to go WAY back tho)

You don't have to go way back to find a CPU without barrel shifter. The Pentium 4 has a 'logarithm shifter'. It's a (conditional) 1-bit shifter followed by a 2-bit shifter, followed by a 4-bit shifter, ... , and finally a 16-bit shifter (for operands up to 32-bit). It works by taking the shift amount and using the first least significant bit (LSB) to determine whether the 1-bit shifter should shift or not, using the second LSB for the 2-bit shifter, etc. This way every combination can be made.

For example shifting X by 5 (binary 1001) is a shift by 1 bit position followed by a shift by 4 bit positions.

The advantage of a log shifter is that it takes less space (less transistors) - a barrel shifter basically does all possible shifts at once and selects the one you need with a multiplexer. But its disadvantage is that it is slower because it takes several stages. This is why on a Pentium 4 shifting is not a fast operation. In fact the assembly optimization manual advises to do small constant shifts to the left with additions and lea instructions. Once again do not change high-level code because of this, it's the compiler's task to perform this optimization when necessary.