固定大小块分配器中的块分配

Question

下面的例程是为库使用而编写的固定大小分配器中的块分配过程。它被设计成可以从C++ (未损坏的符号名为void * Superblock::alloc_block())访问。这个例程的性能对库来说是至关重要的；而我，几乎没有在装配方面的经验，我正在寻找关于性能的建议，以及逻辑中的任何漏洞。它现在似乎工作正常，但我担心的是边缘案件。

执行上下文:为x86_64系统V编写的，在这里可以找到完整的分配器：https://github.com/cmura81/experimental-allocator。

alloc_sb_alloc_block.s.s：

.globl __ZN10Superblock11alloc_blockEv

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

__ZN10Superblock11alloc_blockEv:
  xorq %rcx, %rcx
  // this->beginning -> rsi
  movq 0(%rdi), %rsi
  // allocated_block = this->last_privately_freed_block
  movq 8(%rdi), %rax
  // if this->last_privately_freed_block == NULL
  testq %rax, %rax
  jz __ZN10Superblock11alloc_blockEv.i_pubchalloc
  // this->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->last_privately_freed_block = this->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->last_publicly_freed_block == NULL
  testq %rax, %rax
  jz __ZN10Superblock11alloc_blockEv.i_noalloc
  // this->free_blocks--
  decw 26(%rdi)

  // if *(uint16_t)(this->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->last_privately_freed_block = this->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

Answer 1

这些评论都与优化有关，而不是“逻辑漏洞”。而且，它们是在没有经过测试的情况下编写的。显然，您需要同时确保正确的函数，以及配置文件，以查看它们是否确实改进了什么。

( 1)作为明显的第一步：

xorq %rcx, %rcx

可以作为

xorq %ecx, %ecx

它产生同样的效果，但它比1字节短。

( 2)看起来您正在使用notw %dx (在两个不同的地方)来查看dx是否是0 0xffff？我可以试试cmp $0xffff, %dx。它长了两个字节，但是如果不是，你就不用“放回去”了(额外的notw %dx花费了3个字节)。

3) (在这一次检查我)您正在使用movslq %edx, %rcx将edx移动到rcx。然而，由于您如何填充edx，我相信它已经清除了上面的位。在这种情况下，一个简单的movq %rdx, %rcx就足够了。

4) __ZN10Superblock11alloc_blockEv.i_pubchalloc循环可能应该插入一个pause。也许是这样的：

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

关于为什么这是一个好主意，请参阅pause上的文档。

这些都很挑剔。因为只有一个循环，所以没有那么多需要优化的东西。