Comments on: Playing with bits

By: M

Sun, 14 Feb 2010 12:44:58 +0000

unsigned int mask = (m_start + size >= m_bottom)-1;

By: ed

ed — Wed, 10 Feb 2010 20:13:19 +0000

errata:
Mask is not reversed. OldStart equals m_start at the beginning, so instead of setting oldStart to m_start using a mask, we will clear to zero when condition is “”"NOT”"” true. Then we just mangle a bit with mask and size, and we clear size when cond = true.
And if I’m not wrong, then this will require one arithmetic less.

By: ed

ed — Wed, 10 Feb 2010 20:11:58 +0000

I took a bit different approach.

unsigned char* oldStart = m_start;
m_start += size;
uint32 mask_sign = (m_start – m_bottom) >> 31;
oldStart &= mask_sign;
size = (mask_sign ^ size) & size;
m_start -= size;

Mask is not reversed. OldStart equals m_start at the beginning, so instead of setting oldStart to m_start using a mask, we will clear to zero when condition is true. Then we just mangle a bit with mask and size, and we clear size when cond = true.
And if I’m not wrong, then this will require one arithmetic less.

By: Arseny Kapoulkine

Arseny Kapoulkine — Wed, 10 Feb 2010 18:21:20 +0000

It’s easy to make it 64-bit proof – just use intptr_t / uintptr_t instead of int/unsigned int and sizeof(intptr_t) * 8 – 1 instead of 31 (well, this assumes a 8-bit byte… :)

By: admin

admin — Wed, 10 Feb 2010 10:33:46 +0000

Sander: almost portable now :) Will probably break with 64-bit pointers.

By: Sander van Rossen

Sander van Rossen — Wed, 10 Feb 2010 09:51:53 +0000

Hmm.. not sure what happened to the above post, but it seems to have swallowed some text..

The essence of it all is the:
INTEGER_BITS = (sizeof(int) * 8),
INTEGER_MAX = (1u << (INTEGER_BITS – 1))

enum part

By: Sander van Rossen

Sander van Rossen — Wed, 10 Feb 2010 09:49:28 +0000

enum IntegerTraits
{
INTEGER_BITS = (sizeof(int) * 8),
INTEGER_MAX = (1u <> (INTEGER_BITS – 1);
const unsigned int mask = ((unsigned int)INTEGER_MAX) – (sign – 1);
oldStart = (unsigned char*)((size_t)m_start & mask);
m_start += size & mask;

Not tested, but shouldn’t this make it portable?

By: admin

admin — Wed, 10 Feb 2010 08:25:34 +0000

IIRC latest GCC is smart enough to use cmov__ whenever it can, I don’t think MSVC will do it, though. It’s not a “real” piece of code we’re trying to optimize here, BTW, just a little brain exercise.
@Arseny: good call, I had a feeling my mask calculation looks a little bit too complicated.

By: sopyer

sopyer — Wed, 10 Feb 2010 07:37:46 +0000

@Joshua

As far as I know x86 assembler has command cmov__ which is available from Pentium Pro processor family. But I am actually unaware about its support by compilers.

By: Joshua

Joshua — Tue, 09 Feb 2010 23:21:59 +0000

sopyer:

Actually, in many compilers (particularly targeting x86 and variants), using conditional assignment actually generates a branch instruction because short of a conditional move (which is only available on newer processors), branching is the fastest way to do it. MIPS and PowerPC both have instructions to do this directly without a branch (slt for Set on Less Than).

Also, the conditional operator (?:) is no better than an if in terms of generating branching instructions. It’s just syntactic sugar.