x86_64 System V呼び出し規約 AT/T記法のアセンブラで赤黒木 (削除は実装していない, 処理速度やコードサイズは未考慮)

asm-red-black-tree.s

#
# x86_64 赤黒木 (System V 呼び出し規約)
# (C) 2013 @YVT, all rights reserved.
#

.global _RedBlack_AllocNode

# .global _RedBlack_FreeNode

# struct TreeDescriptor {
#   TreeNode *root;
# }
# struct TreeNode {
#   u64 key;
#   u64 value;
#   TreeNode *left;
#   TreeNode *right;
#	TreeNode *parent;
#   u8 isRed;
# }

# ======================================
.global _RedBlack_Insert
_RedBlack_Insert:
	# %rdi: TreeDescriptor *
	# %rsi: u64 key
	# %rdx: u64 value
	pushq	%rbp
	movq	%rsp, %rbp
	pushq	%r12
	pushq	%r13
	pushq	%r14
	pushq	%rbx

	# --- finds insertion position
	# %r12: TreeNode **insertPos
	# %r13: TreeNode *parent
	movq	%rdi, %r12
	movq	$0, %r13
L_RedBlack_Insert_1:
	# %r8:	TreeNode *
	movq	(%r12), %r8
	test	%r8, %r8
	je		L_RedBlack_Insert_2

	movq	%r8, %r13

	# - compare key
	cmp		%rsi, (%r8)
	je		L_RedBlack_Insert_1eq
	jl		L_RedBlack_Insert_1gt

	# %r9:  TreeNode *child
L_RedBlack_Insert_1lt:
	cmpq	$0, 16(%r8)
	lea		16(%r8), %r12
	jne		L_RedBlack_Insert_1
	jmp		L_RedBlack_Insert_2
L_RedBlack_Insert_1eq:
	cmpq	$0, 16(%r8)
	je		L_RedBlack_Insert_1lt
	# jmp	L_RedBlack_Insert_1gt  (fall through)
L_RedBlack_Insert_1gt:
	cmpq	$0, 24(%r8)
	lea		24(%r8), %r12
	jne		L_RedBlack_Insert_1
	# jmp	L_RedBlack_Insert_2 (fall through)


L_RedBlack_Insert_2:

	# %r8:	(discarded)
	pushq	%rsi
	pushq	%rdi
	call	_RedBlack_AllocNode
	popq	%rdi
	popq	%rsi
	# %rax:	TreeNode *
	movq	%rsi, (%rax)	# key
	movq	%rdi, 8(%rax)	# value
	movq	$0, 16(%rax)	# left
	movq	$0,	24(%rax)	# right
	movq	%r13, 32(%rax)	# parent
	movb	$1, 40(%rax)	# RED
	movq	%rax, (%r12)	# set leaf

	# %rbx: TreeNode * returned
	movq	%rax, %rbx

L_RedBlack_Insert_2b:
	# %r12: (invalid)
	# %r13:	TreeNode *parent == rax->parent

	# no parent?
	test	%r13, %r13
	jne		L_RedBlack_Insert_3

	movb	$0, 40(%rax)	# BLACK

	jmp		L_RedBlack_Insert_e


L_RedBlack_Insert_3:
	# has parent. check the parent color.
	movb	40(%r13), %bl	# parent->color
	test	%bl, %bl
	jne		L_RedBlack_Insert_4 # parent is red
	jmp		L_RedBlack_Insert_e


L_RedBlack_Insert_4:
	# %r14:	TreeNode *uncle
	movq	32(%r13), %r14	# parent->parent
	cmpq	%r13, 16(%r14)	# parent == parent->parent->left?
	je L_RedBlack_Insert_4a
	movq	16(%r14), %r14
	jmp L_RedBlack_Insert_4b
L_RedBlack_Insert_4a:
	movq	24(%r14), %r14
	# fall-through
L_RedBlack_Insert_4b:

	test	%r14, %r14		# uncle == nullptr?
	je		L_RedBlack_Insert_5

	cmpb	$0, 40(%r14)	# uncle->color == BLACK?
	je		L_RedBlack_Insert_5

	movb	$0, 40(%r13)	# parent->color = BLACK
	movb	$0, 40(%r14)	# uncle->color = BLACK
	movq	32(%r14), %r14	# r14 <- uncle->parent == grandparent
	movb	$1, 40(%r14)	# grandparent->color = BLACK

	movq	%r14, %rax
	movq	32(%rax), %r13
	jmp		L_RedBlack_Insert_2b # repeat process for grand-parent

L_RedBlack_Insert_5:
	# %r14: TreeNode *grandparent
	movq	32(%r13), %r14
	cmpq	%rax, 24(%r13)	# node != parent->right
	jne		L_RedBlack_Insert_6
	cmpq	%r13, 16(%r14) # parent != grandparent->left
	jne		L_RedBlack_Insert_6

	movq	%r13, %rsi
	pushq	%rax
	call	_RedBlack_RotateLeft
	popq	%rax

	movq	16(%rax), %rax
	movq	32(%rax), %r13
	jmp		L_RedBlack_Insert_7

L_RedBlack_Insert_6:
	cmpq	%rax, 16(%r13)	# node != parent->left
	jne		L_RedBlack_Insert_7
	cmpq	%r13, 24(%r14) # parent != grandparent->right
	jne		L_RedBlack_Insert_7

	movq	%r13, %rsi
	pushq	%rax
	call	_RedBlack_RotateRight
	popq	%rax

	movq	24(%rax), %rax
	movq	32(%rax), %r13

	# fall-through
L_RedBlack_Insert_7:
	# %r14: TreeNode *grandparent
	movq	32(%r13), %r14

	movb	$0, 40(%r13)	# parent->color = BLACK
	movb	$1, 40(%r14)	# grandparent->color = BLACK
	cmpq	%r13, 16(%r14)	# parent == grandparent->left

	movq	%r14, %rsi

	pushq	%rax
	je		L_RedBlack_Insert_7a
	call	_RedBlack_RotateLeft
	jmp		L_RedBlack_Insert_7b
L_RedBlack_Insert_7a:
	call	_RedBlack_RotateRight
L_RedBlack_Insert_7b:
	popq	%rax

	# fall-through

L_RedBlack_Insert_e:
	# %rax:	TreeNode *node
	movq	%rbx, %rax
	popq	%rbx
	popq	%r14
	popq	%r13
	popq	%r12
	popq	%rbp
	ret
	# %rax: (return) TreeNode *


# ======================================
_RedBlack_RotateLeft:
	# %rdi: TreeDescriptor *
	# %rsi: TreeNode *
	pushq	%rbp
	movq	%rsp, %rbp

	# %r9:	TreeNode **pos where *pos = node
	movq	32(%rsi), %r9
	test	%r9, %r9
	jne		_RedBlack_RotateLeft_1a
	movq	%rdi, %r9
	jmp		_RedBlack_RotateLeft_1b
_RedBlack_RotateLeft_1a:
	cmpq	16(%r9), %rsi
	jne		_RedBlack_RotateLeft_1c
	lea		16(%r9), %r9
	jmp		_RedBlack_RotateLeft_1b
_RedBlack_RotateLeft_1c:
	lea		24(%r9), %r9
_RedBlack_RotateLeft_1b:

	movq	24(%rsi), %r8
	movq	16(%r8), %r11
	movq	%r11, 24(%rsi)
	cmpq	$0, 16(%r8)
	je		_RedBlack_RotateLeft_2
	movq	16(%r8), %r10
	movq	%rsi, 32(%r10)
_RedBlack_RotateLeft_2:
	movq	32(%rsi), %r11
	movq	%r11, 32(%r8)
	movq	%r8, (%r9)
	movq	%rsi, 16(%r8)
	movq	%r8, 32(%rsi)
	
	popq	%rbp
	ret
# ======================================
_RedBlack_RotateRight:
	# %rdi: TreeDescriptor *
	# %rsi: TreeNode *
	pushq	%rbp
	movq	%rsp, %rbp

	# %r9:	TreeNode **pos where *pos = node
	movq	32(%rsi), %r9
	test	%r9, %r9
	jne		_RedBlack_RotateRight_1a
	movq	%rdi, %r9
	jmp		_RedBlack_RotateRight_1b
_RedBlack_RotateRight_1a:
	cmpq	16(%r9), %rsi
	jne		_RedBlack_RotateRight_1c
	lea		16(%r9), %r9
	jmp		_RedBlack_RotateRight_1b
_RedBlack_RotateRight_1c:
	lea		24(%r9), %r9
_RedBlack_RotateRight_1b:

	movq	16(%rsi), %r8
	movq	24(%r8), %r11
	movq	%r11, 16(%rsi)
	cmpq	$0, 24(%r8)
	je		_RedBlack_RotateRight_2
	movq	24(%r8), %r10
	movq	%rsi, 32(%r10)
_RedBlack_RotateRight_2:
	movq	32(%rsi), %r11
	movq	%r11, 32(%r8)
	movq	%r8, (%r9)
	movq	%rsi, 24(%r8)
	movq	%r8, 32(%rsi)
	
	popq	%rbp
	ret

test.cpp

/*
 * 赤黒木ルーチンをテスト・ベンチマークするためのコード達
 * (C) 2013 @YVT, all rights reserved.
 */

#include <cstdlib>
#include <cstdio>
#include <cstdint>
#include <iostream>
#include <chrono>
#include <map>
#include <map>

static double GetHighResClock() {
	using high_res_clock = std::chrono::high_resolution_clock;
	auto now = high_res_clock::now();
	return (double)std::chrono::duration_cast<std::chrono::microseconds>
	(now.time_since_epoch()).count();
}

struct TreeNode;
struct TreeDescriptor;

struct TreeNode
{
	uint64_t key;
	uint64_t value;
	TreeNode *left;
	TreeNode *right;
	TreeNode *parent;
	uint64_t isRed;
	
	void Print(int level)
	{
		auto ind = [level]()
		{
			for(int i = 0; i < level; i++)
				std::cout << "  ";
		};
		ind();
		std::cout << (isRed ? "[Red] " : "[   ] ");
		std::cout << key << std::endl;
		if(left == nullptr && right == nullptr)
			return;
		if(left)
			left->Print(level + 1);
		else
		{
			ind();
			std::cout << "  --" << std::endl;
		}
		if(right)
			right->Print(level + 1);
		else
		{
			ind();
			std::cout << "  --" << std::endl;
		}
	}
};

struct TreeDescriptor
{
	TreeNode *root;
	TreeDescriptor():
	root(nullptr)
	{
		
	}
	void Print()
	{
		std::cout << "-- tree --" << std::endl;
		if(root)
			root->Print(0);
	}
};


extern "C" TreeNode *RedBlack_AllocNode() {
	return new TreeNode();
}

extern "C" TreeNode *RedBlack_Insert(TreeDescriptor *tree, uint64_t key, uint64_t value);



int main()
{
	TreeDescriptor tree;
	double time;
	std::map<uint64_t, uint64_t> stlMap;
	
	time = GetHighResClock();
	for(int i = 0; i < 1000000; i++) {
		uint64_t key = std::rand() % 100;
		//std::cout << "Inserting " << key << std::endl;
		RedBlack_Insert(&tree, key, key);
	}
	std::cout << "RedBlack = " << (GetHighResClock() - time) << std::endl;
	
	
	time = GetHighResClock();
	for(int i = 0; i < 1000000; i++) {
		uint64_t key = std::rand() % 100;
		stlMap.insert(std::make_pair(key, key));
	}
	std::cout << "STL = " << (GetHighResClock() - time) << std::endl;
	
	tree = TreeDescriptor();
	for(int i = 0; i < 10; i++) {
		uint64_t key = std::rand() % 100;
		//std::cout << "Inserting " << key << std::endl;
		RedBlack_Insert(&tree, key, key);
	}
	
	tree.Print();
	return 0;
}

Core i7 1.4GHz Ivy Bridge OS X v10.9:

$ clang++ brt.s brt-c.cpp -std=c++11 -g
$ ./a.out
RedBlack = 562144
STL = 324889
-- tree --
[   ] 34
  [Red] 19
    [   ] 16
      [Red] 3
      --
    [   ] 22
      --
      [Red] 23
  [Red] 38
    [   ] 34
    [   ] 95
      [Red] 47
      --

$ clang++ brt.s brt-c.cpp -std=c++11 -O4
$ ./a.out
RedBlack = 543079
STL = 123370
-- tree --
[   ] 34
  [Red] 19
    [   ] 16
      [Red] 3
      --
    [   ] 22
      --
      [Red] 23
  [Red] 38
    [   ] 34
    [   ] 95
      [Red] 47
      --