Block Allocation in Fixed-Size Block Allocator The following routine is the block-allocation procedure in a fixed-size allocator being written for library use. It is designed to be accessed from C++ (the un-mangled symbol name is void * Superblock::alloc_block()). The performance of this routine is the critical to the library; and I, with almost no prior experience in assembly, am looking for suggestions about performance and also any holes in the logic. It seems to be working correctly right now, but I'm worried about edge cases.

Execution context: written for x86_64 System V abi, full allocator may be found here: https://github.com/cmura81/experimental-allocator.

alloc_sb_alloc_block.s:



.globl __ZN10Superblock11alloc_blockEv

// 'this is passed in %rdi
// Variables:
//    this-&gt;beginning = 0(%rdi) +8
//    this-&gt;last_privately_freed_block = 8(%rdi) +8
//    this-&gt;last_publicly_freed_block = 16(%rdi) +8
//    this-&gt;block_size = 24(%rdi) +2
//    this-&gt;free_blocks = 26(%rdi) +2
//    this-&gt;max_blocks = 28(%rdi) +2

__ZN10Superblock11alloc_blockEv:
  xorq %rcx, %rcx
  // this-&gt;beginning -&gt; rsi
  movq 0(%rdi), %rsi
  // allocated_block = this-&gt;last_privately_freed_block
  movq 8(%rdi), %rax
  // if this-&gt;last_privately_freed_block == NULL
  testq %rax, %rax
  jz __ZN10Superblock11alloc_blockEv.i_pubchalloc
  // this-&gt;free_blocks--
  decw 26(%rdi)

  // Move 2 bytes from rax into edx
  movzwl (%rax), %edx
  notw %dx
  jz __ZN10Superblock11alloc_blockEv.i_nbi_ffff
  notw %dx
  movslq %edx, %rcx
  // this-&gt;last_privately_freed_block = this-&gt;beginning + next_block_index
  addq %rcx, %rsi
  movq %rsi, 8(%rdi)

  ret
__ZN10Superblock11alloc_blockEv.i_nbi_ffff:
  movq $0, 8(%rdi)
  ret
__ZN10Superblock11alloc_blockEv.i_pubchalloc:
  movq 16(%rdi), %rax
  // if this-&gt;last_publicly_freed_block == NULL
  testq %rax, %rax
  jz __ZN10Superblock11alloc_blockEv.i_noalloc
  // this-&gt;free_blocks--
  decw 26(%rdi)

  // if *(uint16_t)(this-&gt;last_publicly_freed_block + next_block_index) == 0xFFFF
  movzwl (%rax), %edx
  notw %dx
  jz __ZN10Superblock11alloc_blockEv.i_pubnbi_ffff
  notw %dx
  movslq %edx, %rcx
  // this-&gt;last_privately_freed_block = this-&gt;beginning + next_block_index
  addq %rcx, %rsi
  movq %rsi, 16(%rdi)
  ret
__ZN10Superblock11alloc_blockEv.i_pubnbi_ffff:
  movq $0, 8(%rdi)
  ret
__ZN10Superblock11alloc_blockEv.i_noalloc:
  movq $0, %rax
  ret
These comments all have to do with optimization, not "logic holes."  Also, they are written without having tested them.  Obviously you'll want to both ensure correct function, and profile to see if they actually improve anything.

1) As an obvious first step:

xorq %rcx, %rcx


can be done as

xorq %ecx, %ecx


It produces the same effect, but it's 1 byte shorter.

2) It looks like you are using notw %dx (in 2 different places) to see if dx is 0xffff?  I might try cmp $0xffff, %dx instead.  It's 2 bytes longer, but you don't have to "put it back" if it's not (the extra notw %dx costs 3 bytes).

3) (Check me on this one) You are using movslq %edx, %rcx to move edx to rcx.  However because of how you populate edx, I believe it already clears the upper bits.  Such being the case, a simple movq %rdx, %rcx might suffice.

4) The __ZN10Superblock11alloc_blockEv.i_pubchalloc loop should probably have a pause inserted.  Perhaps something like this:

__ZN10Superblock11alloc_blockEv.i_pubchalloc2:
  pause
__ZN10Superblock11alloc_blockEv.i_pubchalloc:
  movq 16(%rdi), %rax
  // if this-&gt;last_publicly_freed_block == NULL
  testq %rax, %rax
  jz __ZN10Superblock11alloc_blockEv.i_pubchalloc2


See the docs on pause for why this is a good idea.

These are all pretty nitpicky.  Since there's only the 1 loop, there's just not that much to optimize.