Sorting algorithms

Discussion of chess software programming and technical issues.

Moderators: hgm, Rebel, chrisw

Dann Corbit
Posts: 12534
Joined: Wed Mar 08, 2006 8:57 pm
Location: Redmond, WA USA

Re: Sorting algorithms

Post by Dann Corbit »

That is a beautiful routine.
Taking ideas is not a vice, it is a virtue. We have another word for this. It is called learning.
But sharing ideas is an even greater virtue. We have another word for this. It is called teaching.
Dann Corbit
Posts: 12534
Joined: Wed Mar 08, 2006 8:57 pm
Location: Redmond, WA USA

Re: Sorting algorithms

Post by Dann Corbit »

As a C++ template:

Code: Select all

#include <iostream>
template <typename Etype>
inline void stable_sorting_network&#40; Etype *begin, Etype *end )
&#123;
    Etype *p, *q, tmp;

    p=begin;
    switch&#40; end - begin ) &#123;
    default&#58;
    case 10&#58;
        &#123; Etype px = p&#91;0&#93;; Etype py = p&#91;1&#93;; Etype tmp = p&#91;0&#93; = px <= py ? px &#58; py; p&#91;1&#93; ^= px ^ tmp; &#125;;
        &#123; Etype px = p&#91;1&#93;; Etype py = p&#91;2&#93;; Etype tmp = p&#91;1&#93; = px <= py ? px &#58; py; p&#91;2&#93; ^= px ^ tmp; &#125;;
        &#123; Etype px = p&#91;2&#93;; Etype py = p&#91;3&#93;; Etype tmp = p&#91;2&#93; = px <= py ? px &#58; py; p&#91;3&#93; ^= px ^ tmp; &#125;;
        &#123; Etype px = p&#91;3&#93;; Etype py = p&#91;4&#93;; Etype tmp = p&#91;3&#93; = px <= py ? px &#58; py; p&#91;4&#93; ^= px ^ tmp; &#125;;
        &#123; Etype px = p&#91;4&#93;; Etype py = p&#91;5&#93;; Etype tmp = p&#91;4&#93; = px <= py ? px &#58; py; p&#91;5&#93; ^= px ^ tmp; &#125;;
        &#123; Etype px = p&#91;5&#93;; Etype py = p&#91;6&#93;; Etype tmp = p&#91;5&#93; = px <= py ? px &#58; py; p&#91;6&#93; ^= px ^ tmp; &#125;;
        &#123; Etype px = p&#91;6&#93;; Etype py = p&#91;7&#93;; Etype tmp = p&#91;6&#93; = px <= py ? px &#58; py; p&#91;7&#93; ^= px ^ tmp; &#125;;
        &#123; Etype px = p&#91;7&#93;; Etype py = p&#91;8&#93;; Etype tmp = p&#91;7&#93; = px <= py ? px &#58; py; p&#91;8&#93; ^= px ^ tmp; &#125;;
        &#123; Etype px = p&#91;8&#93;; Etype py = p&#91;9&#93;; Etype tmp = p&#91;8&#93; = px <= py ? px &#58; py; p&#91;9&#93; ^= px ^ tmp; &#125;;
    case 9&#58;
        &#123; Etype px = p&#91;0&#93;; Etype py = p&#91;1&#93;; Etype tmp = p&#91;0&#93; = px <= py ? px &#58; py; p&#91;1&#93; ^= px ^ tmp; &#125;;
        &#123; Etype px = p&#91;1&#93;; Etype py = p&#91;2&#93;; Etype tmp = p&#91;1&#93; = px <= py ? px &#58; py; p&#91;2&#93; ^= px ^ tmp; &#125;;
        &#123; Etype px = p&#91;2&#93;; Etype py = p&#91;3&#93;; Etype tmp = p&#91;2&#93; = px <= py ? px &#58; py; p&#91;3&#93; ^= px ^ tmp; &#125;;
        &#123; Etype px = p&#91;3&#93;; Etype py = p&#91;4&#93;; Etype tmp = p&#91;3&#93; = px <= py ? px &#58; py; p&#91;4&#93; ^= px ^ tmp; &#125;;
        &#123; Etype px = p&#91;4&#93;; Etype py = p&#91;5&#93;; Etype tmp = p&#91;4&#93; = px <= py ? px &#58; py; p&#91;5&#93; ^= px ^ tmp; &#125;;
        &#123; Etype px = p&#91;5&#93;; Etype py = p&#91;6&#93;; Etype tmp = p&#91;5&#93; = px <= py ? px &#58; py; p&#91;6&#93; ^= px ^ tmp; &#125;;
        &#123; Etype px = p&#91;6&#93;; Etype py = p&#91;7&#93;; Etype tmp = p&#91;6&#93; = px <= py ? px &#58; py; p&#91;7&#93; ^= px ^ tmp; &#125;;
        &#123; Etype px = p&#91;7&#93;; Etype py = p&#91;8&#93;; Etype tmp = p&#91;7&#93; = px <= py ? px &#58; py; p&#91;8&#93; ^= px ^ tmp; &#125;;
    case 8&#58;
        &#123; Etype px = p&#91;0&#93;; Etype py = p&#91;1&#93;; Etype tmp = p&#91;0&#93; = px <= py ? px &#58; py; p&#91;1&#93; ^= px ^ tmp; &#125;;
        &#123; Etype px = p&#91;1&#93;; Etype py = p&#91;2&#93;; Etype tmp = p&#91;1&#93; = px <= py ? px &#58; py; p&#91;2&#93; ^= px ^ tmp; &#125;;
        &#123; Etype px = p&#91;2&#93;; Etype py = p&#91;3&#93;; Etype tmp = p&#91;2&#93; = px <= py ? px &#58; py; p&#91;3&#93; ^= px ^ tmp; &#125;;
        &#123; Etype px = p&#91;3&#93;; Etype py = p&#91;4&#93;; Etype tmp = p&#91;3&#93; = px <= py ? px &#58; py; p&#91;4&#93; ^= px ^ tmp; &#125;;
        &#123; Etype px = p&#91;4&#93;; Etype py = p&#91;5&#93;; Etype tmp = p&#91;4&#93; = px <= py ? px &#58; py; p&#91;5&#93; ^= px ^ tmp; &#125;;
        &#123; Etype px = p&#91;5&#93;; Etype py = p&#91;6&#93;; Etype tmp = p&#91;5&#93; = px <= py ? px &#58; py; p&#91;6&#93; ^= px ^ tmp; &#125;;
        &#123; Etype px = p&#91;6&#93;; Etype py = p&#91;7&#93;; Etype tmp = p&#91;6&#93; = px <= py ? px &#58; py; p&#91;7&#93; ^= px ^ tmp; &#125;;
    case 7&#58;
        &#123; Etype px = p&#91;0&#93;; Etype py = p&#91;1&#93;; Etype tmp = p&#91;0&#93; = px <= py ? px &#58; py; p&#91;1&#93; ^= px ^ tmp; &#125;;
        &#123; Etype px = p&#91;1&#93;; Etype py = p&#91;2&#93;; Etype tmp = p&#91;1&#93; = px <= py ? px &#58; py; p&#91;2&#93; ^= px ^ tmp; &#125;;
        &#123; Etype px = p&#91;2&#93;; Etype py = p&#91;3&#93;; Etype tmp = p&#91;2&#93; = px <= py ? px &#58; py; p&#91;3&#93; ^= px ^ tmp; &#125;;
        &#123; Etype px = p&#91;3&#93;; Etype py = p&#91;4&#93;; Etype tmp = p&#91;3&#93; = px <= py ? px &#58; py; p&#91;4&#93; ^= px ^ tmp; &#125;;
        &#123; Etype px = p&#91;4&#93;; Etype py = p&#91;5&#93;; Etype tmp = p&#91;4&#93; = px <= py ? px &#58; py; p&#91;5&#93; ^= px ^ tmp; &#125;;
        &#123; Etype px = p&#91;5&#93;; Etype py = p&#91;6&#93;; Etype tmp = p&#91;5&#93; = px <= py ? px &#58; py; p&#91;6&#93; ^= px ^ tmp; &#125;;
    case 6&#58;
        &#123; Etype px = p&#91;0&#93;; Etype py = p&#91;1&#93;; Etype tmp = p&#91;0&#93; = px <= py ? px &#58; py; p&#91;1&#93; ^= px ^ tmp; &#125;;
        &#123; Etype px = p&#91;1&#93;; Etype py = p&#91;2&#93;; Etype tmp = p&#91;1&#93; = px <= py ? px &#58; py; p&#91;2&#93; ^= px ^ tmp; &#125;;
        &#123; Etype px = p&#91;2&#93;; Etype py = p&#91;3&#93;; Etype tmp = p&#91;2&#93; = px <= py ? px &#58; py; p&#91;3&#93; ^= px ^ tmp; &#125;;
        &#123; Etype px = p&#91;3&#93;; Etype py = p&#91;4&#93;; Etype tmp = p&#91;3&#93; = px <= py ? px &#58; py; p&#91;4&#93; ^= px ^ tmp; &#125;;
        &#123; Etype px = p&#91;4&#93;; Etype py = p&#91;5&#93;; Etype tmp = p&#91;4&#93; = px <= py ? px &#58; py; p&#91;5&#93; ^= px ^ tmp; &#125;;
    case 5&#58;
        &#123; Etype px = p&#91;0&#93;; Etype py = p&#91;1&#93;; Etype tmp = p&#91;0&#93; = px <= py ? px &#58; py; p&#91;1&#93; ^= px ^ tmp; &#125;;
        &#123; Etype px = p&#91;1&#93;; Etype py = p&#91;2&#93;; Etype tmp = p&#91;1&#93; = px <= py ? px &#58; py; p&#91;2&#93; ^= px ^ tmp; &#125;;
        &#123; Etype px = p&#91;2&#93;; Etype py = p&#91;3&#93;; Etype tmp = p&#91;2&#93; = px <= py ? px &#58; py; p&#91;3&#93; ^= px ^ tmp; &#125;;
        &#123; Etype px = p&#91;3&#93;; Etype py = p&#91;4&#93;; Etype tmp = p&#91;3&#93; = px <= py ? px &#58; py; p&#91;4&#93; ^= px ^ tmp; &#125;;
    case 4&#58;
        &#123; Etype px = p&#91;0&#93;; Etype py = p&#91;1&#93;; Etype tmp = p&#91;0&#93; = px <= py ? px &#58; py; p&#91;1&#93; ^= px ^ tmp; &#125;;
        &#123; Etype px = p&#91;1&#93;; Etype py = p&#91;2&#93;; Etype tmp = p&#91;1&#93; = px <= py ? px &#58; py; p&#91;2&#93; ^= px ^ tmp; &#125;;
        &#123; Etype px = p&#91;2&#93;; Etype py = p&#91;3&#93;; Etype tmp = p&#91;2&#93; = px <= py ? px &#58; py; p&#91;3&#93; ^= px ^ tmp; &#125;;
    case 3&#58;
        &#123; Etype px = p&#91;0&#93;; Etype py = p&#91;1&#93;; Etype tmp = p&#91;0&#93; = px <= py ? px &#58; py; p&#91;1&#93; ^= px ^ tmp; &#125;;
        &#123; Etype px = p&#91;1&#93;; Etype py = p&#91;2&#93;; Etype tmp = p&#91;1&#93; = px <= py ? px &#58; py; p&#91;2&#93; ^= px ^ tmp; &#125;;
    case 2&#58;
        &#123; Etype px = p&#91;0&#93;; Etype py = p&#91;1&#93;; Etype tmp = p&#91;0&#93; = px <= py ? px &#58; py; p&#91;1&#93; ^= px ^ tmp; &#125;;
    case 1&#58;
    case 0&#58;
        break;
    &#125;


    for ( p = begin + 10; p < end; ++p ) &#123;
        tmp = *p;
        for ( q = p; q != begin && *( q-1 ) > tmp; --q )
            *q = *( q-1 );
        *q = tmp;
    &#125;
&#125;

int arrdat&#91;&#93; = &#123; 9, 6, 23, 4, 5, 6, 7, 11, 2, 3, 1, 5, 9, 11, 0, 13, -8, 3, 4, 5, 6, 3, 2, 1 &#125;;

int main&#40; void )
&#123;
    static const size_t adim = sizeof arrdat / sizeof arrdat&#91;0&#93;;
    size_t index;
    stable_sorting_network <int> ( &arrdat&#91;0&#93;, &arrdat&#91;adim-1&#93; );
    for ( index = 0; index < adim; index++ )
        std&#58;&#58;cout << arrdat&#91;index&#93; << std&#58;&#58;endl;
    return 0;
&#125;
The top sorting network still remains branchless (at least if you are sorting an array of int):

Code: Select all

	.file	"snet.cpp"
	.section	.text$_ZNKSt5ctypeIcE8do_widenEc,"x"
	.linkonce discard
	.align 2
	.p2align 4,,15
	.globl	_ZNKSt5ctypeIcE8do_widenEc
	.def	_ZNKSt5ctypeIcE8do_widenEc;	.scl	2;	.type	32;	.endef
	.seh_proc	_ZNKSt5ctypeIcE8do_widenEc
_ZNKSt5ctypeIcE8do_widenEc&#58;
.LFB1288&#58;
	.seh_endprologue
	movl	%edx, %eax
	ret
	.seh_endproc
	.text
	.p2align 4,,15
	.def	__tcf_0;	.scl	3;	.type	32;	.endef
	.seh_proc	__tcf_0
__tcf_0&#58;
.LFB1975&#58;
	.seh_endprologue
	leaq	_ZStL8__ioinit&#40;%rip&#41;, %rcx
	jmp	_ZNSt8ios_base4InitD1Ev
	.seh_endproc
	.def	__main;	.scl	2;	.type	32;	.endef
	.section	.text.startup,"x"
	.p2align 4,,15
	.globl	main
	.def	main;	.scl	2;	.type	32;	.endef
	.seh_proc	main
main&#58;
.LFB1532&#58;
	pushq	%r13
	.seh_pushreg	%r13
	pushq	%r12
	.seh_pushreg	%r12
	pushq	%rbp
	.seh_pushreg	%rbp
	pushq	%rdi
	.seh_pushreg	%rdi
	pushq	%rsi
	.seh_pushreg	%rsi
	pushq	%rbx
	.seh_pushreg	%rbx
	subq	$40, %rsp
	.seh_stackalloc	40
	.seh_endprologue
	call	__main
	movl	4+arrdat&#40;%rip&#41;, %ecx
	movl	arrdat&#40;%rip&#41;, %eax
	movl	8+arrdat&#40;%rip&#41;, %r8d
	movl	12+arrdat&#40;%rip&#41;, %r9d
	movl	16+arrdat&#40;%rip&#41;, %r10d
	movl	20+arrdat&#40;%rip&#41;, %r11d
	cmpl	%ecx, %eax
	movl	%ecx, %edx
	movl	24+arrdat&#40;%rip&#41;, %ebx
	cmovle	%eax, %edx
	xorl	%ecx, %eax
	movl	%r8d, %ecx
	xorl	%edx, %eax
	movl	28+arrdat&#40;%rip&#41;, %esi
	movl	32+arrdat&#40;%rip&#41;, %edi
	cmpl	%r8d, %eax
	movl	36+arrdat&#40;%rip&#41;, %ebp
	cmovle	%eax, %ecx
	xorl	%r8d, %eax
	movl	%r9d, %r8d
	xorl	%ecx, %eax
	cmpl	%r9d, %eax
	cmovle	%eax, %r8d
	xorl	%r9d, %eax
	movl	%r10d, %r9d
	xorl	%r8d, %eax
	movl	%r8d, %r12d
	cmpl	%r10d, %eax
	cmovle	%eax, %r9d
	xorl	%r10d, %eax
	movl	%r11d, %r10d
	xorl	%r9d, %eax
	cmpl	%r11d, %eax
	cmovle	%eax, %r10d
	xorl	%r11d, %eax
	movl	%ebx, %r11d
	xorl	%r10d, %eax
	cmpl	%ebx, %eax
	cmovle	%eax, %r11d
	xorl	%ebx, %eax
	movl	%esi, %ebx
	xorl	%r11d, %eax
	cmpl	%esi, %eax
	cmovle	%eax, %ebx
	xorl	%esi, %eax
	movl	%edi, %esi
	xorl	%ebx, %eax
	cmpl	%edi, %eax
	cmovle	%eax, %esi
	xorl	%edi, %eax
	movl	%ebp, %edi
	xorl	%esi, %eax
	cmpl	%ebp, %eax
	cmovle	%eax, %edi
	xorl	%ebp, %eax
	movl	%ecx, %ebp
	xorl	%edi, %eax
	cmpl	%ecx, %edx
	cmovle	%edx, %ebp
	xorl	%ecx, %edx
	movl	%r9d, %ecx
	xorl	%ebp, %edx
	movl	%eax, 36+arrdat&#40;%rip&#41;
	cmpl	%r8d, %edx
	cmovle	%edx, %r12d
	xorl	%r8d, %edx
	movl	%r10d, %r8d
	xorl	%r12d, %edx
	cmpl	%r9d, %edx
	cmovle	%edx, %ecx
	xorl	%r9d, %edx
	movl	%r11d, %r9d
	xorl	%ecx, %edx
	cmpl	%r10d, %edx
	cmovle	%edx, %r8d
	xorl	%r10d, %edx
	movl	%ebx, %r10d
	xorl	%r8d, %edx
	cmpl	%r11d, %edx
	cmovle	%edx, %r9d
	xorl	%r11d, %edx
	movl	%edi, %r11d
	xorl	%r9d, %edx
	cmpl	%ebx, %edx
	movl	%edx, %eax
	cmovle	%edx, %r10d
	xorl	%ebx, %eax
	movl	%esi, %edx
	xorl	%r10d, %eax
	movl	%ebp, %ebx
	cmpl	%esi, %eax
	cmovle	%eax, %edx
	xorl	%esi, %eax
	movl	%ecx, %esi
	xorl	%edx, %eax
	cmpl	%edi, %eax
	cmovle	%eax, %r11d
	xorl	%edi, %eax
	movl	%r8d, %edi
	xorl	%r11d, %eax
	cmpl	%ebp, %r12d
	cmovle	%r12d, %ebx
	xorl	%r12d, %ebp
	movl	%eax, 32+arrdat&#40;%rip&#41;
	xorl	%ebx, %ebp
	cmpl	%ecx, %ebp
	cmovle	%ebp, %esi
	xorl	%ebp, %ecx
	xorl	%esi, %ecx
	cmpl	%r8d, %ecx
	cmovle	%ecx, %edi
	xorl	%ecx, %r8d
	movl	%r9d, %ecx
	xorl	%edi, %r8d
	cmpl	%r9d, %r8d
	cmovle	%r8d, %ecx
	xorl	%r8d, %r9d
	movl	%r10d, %r8d
	xorl	%ecx, %r9d
	cmpl	%r10d, %r9d
	cmovle	%r9d, %r8d
	xorl	%r9d, %r10d
	movl	%edx, %r9d
	xorl	%r8d, %r10d
	cmpl	%edx, %r10d
	cmovle	%r10d, %r9d
	xorl	%edx, %r10d
	movl	%r11d, %edx
	movl	%r10d, %eax
	movl	%ebx, %r10d
	xorl	%r9d, %eax
	cmpl	%r11d, %eax
	cmovle	%eax, %edx
	xorl	%r11d, %eax
	movl	%edi, %r11d
	xorl	%edx, %eax
	cmpl	%ebx, %esi
	cmovle	%esi, %r10d
	xorl	%esi, %ebx
	movl	%eax, 28+arrdat&#40;%rip&#41;
	xorl	%r10d, %ebx
	movl	%r8d, %esi
	cmpl	%edi, %ebx
	cmovle	%ebx, %r11d
	xorl	%ebx, %edi
	movl	%ecx, %ebx
	xorl	%r11d, %edi
	cmpl	%ecx, %edi
	cmovle	%edi, %ebx
	xorl	%edi, %ecx
	xorl	%ebx, %ecx
	movl	%ebx, %edi
	cmpl	%r8d, %ecx
	movl	%ecx, %eax
	cmovle	%ecx, %esi
	xorl	%r8d, %eax
	movl	%r9d, %ecx
	xorl	%esi, %eax
	movl	%edx, %r8d
	cmpl	%r9d, %eax
	cmovle	%eax, %ecx
	xorl	%r9d, %eax
	movl	%r10d, %r9d
	xorl	%ecx, %eax
	cmpl	%edx, %eax
	cmovle	%eax, %r8d
	xorl	%edx, %eax
	xorl	%r8d, %eax
	cmpl	%r10d, %r11d
	cmovle	%r11d, %r9d
	xorl	%r11d, %r10d
	movl	%esi, %r11d
	xorl	%r9d, %r10d
	movl	%eax, 24+arrdat&#40;%rip&#41;
	cmpl	%ebx, %r10d
	cmovle	%r10d, %edi
	xorl	%r10d, %ebx
	movl	%ecx, %r10d
	xorl	%edi, %ebx
	cmpl	%esi, %ebx
	cmovle	%ebx, %r11d
	xorl	%esi, %ebx
	xorl	%r11d, %ebx
	cmpl	%ecx, %ebx
	movl	%ebx, %eax
	cmovle	%ebx, %r10d
	xorl	%ecx, %eax
	xorl	%r10d, %eax
	cmpl	%eax, %r8d
	movl	%eax, %ebx
	cmovle	%r8d, %ebx
	xorl	%r8d, %eax
	movl	%edi, %r8d
	xorl	%ebx, %eax
	cmpl	%edi, %r9d
	cmovle	%r9d, %r8d
	xorl	%edi, %r9d
	movl	%eax, 20+arrdat&#40;%rip&#41;
	xorl	%r8d, %r9d
	movl	%r11d, %eax
	cmpl	%r11d, %r9d
	cmovle	%r9d, %eax
	xorl	%r11d, %r9d
	movl	%r9d, %edx
	xorl	%eax, %edx
	cmpl	%edx, %r10d
	movl	%edx, %r11d
	cmovle	%r10d, %r11d
	xorl	%r10d, %edx
	leaq	44+arrdat&#40;%rip&#41;, %r10
	xorl	%r11d, %edx
	movl	%r11d, %r9d
	cmpl	%edx, %ebx
	movl	%edx, %ecx
	cmovle	%ebx, %ecx
	xorl	%ebx, %edx
	xorl	%ecx, %edx
	cmpl	%r8d, %eax
	movl	%edx, 16+arrdat&#40;%rip&#41;
	movl	%r8d, %edx
	cmovle	%eax, %edx
	xorl	%r8d, %eax
	xorl	%edx, %eax
	cmpl	%r11d, %eax
	cmovle	%eax, %r9d
	xorl	%r11d, %eax
	leaq	92+arrdat&#40;%rip&#41;, %r11
	xorl	%r9d, %eax
	cmpl	%eax, %ecx
	movl	%eax, %r8d
	cmovle	%ecx, %r8d
	xorl	%ecx, %eax
	movl	%r9d, %ecx
	xorl	%r8d, %eax
	cmpl	%r9d, %edx
	cmovle	%edx, %ecx
	xorl	%r9d, %edx
	movl	%eax, 12+arrdat&#40;%rip&#41;
	xorl	%ecx, %edx
	movl	%r8d, %eax
	leaq	40+arrdat&#40;%rip&#41;, %r9
	cmpl	%r8d, %edx
	cmovle	%edx, %eax
	xorl	%r8d, %edx
	leaq	arrdat&#40;%rip&#41;, %r8
	xorl	%eax, %edx
	cmpl	%ecx, %eax
	movl	%edx, 8+arrdat&#40;%rip&#41;
	movl	%ecx, %edx
	cmovle	%eax, %edx
	xorl	%ecx, %eax
	xorl	%edx, %eax
	cmpq	%r8, %r9
	movl	%edx, arrdat&#40;%rip&#41;
	movl	%eax, 4+arrdat&#40;%rip&#41;
	movq	%r9, %rax
	movl	(%r9&#41;, %ecx
	je	.L5
	.p2align 4,,10
.L21&#58;
	movl	-8&#40;%r10&#41;, %edx
	cmpl	%ecx, %edx
	jg	.L8
	jmp	.L6
	.p2align 4,,10
.L9&#58;
	movl	-4&#40;%rax&#41;, %edx
	cmpl	%edx, %ecx
	jge	.L6
.L8&#58;
	movl	%edx, (%rax&#41;
	subq	$4, %rax
	cmpq	%r8, %rax
	jne	.L9
.L6&#58;
	cmpq	%r11, %r10
	movl	%ecx, (%rax&#41;
	jnb	.L20
.L10&#58;
	addq	$4, %r9
	addq	$4, %r10
	movl	(%r9&#41;, %ecx
	cmpq	%r8, %r9
	movq	%r9, %rax
	jne	.L21
.L5&#58;
	movl	%ecx, (%r9&#41;
	jmp	.L10
.L20&#58;
	leaq	arrdat&#40;%rip&#41;, %rsi
	leaq	96+arrdat&#40;%rip&#41;, %r12
	movq	.refptr._ZSt4cout&#40;%rip&#41;, %rbp
	leaq	_ZNKSt5ctypeIcE8do_widenEc&#40;%rip&#41;, %r13
	jmp	.L14
	.p2align 4,,10
.L24&#58;
	movsbl	67&#40;%rbx&#41;, %edx
.L13&#58;
	movq	%rdi, %rcx
	addq	$4, %rsi
	call	_ZNSo3putEc
	movq	%rax, %rcx
	call	_ZNSo5flushEv
	cmpq	%rsi, %r12
	je	.L22
.L14&#58;
	movl	(%rsi&#41;, %edx
	movq	%rbp, %rcx
	call	_ZNSolsEi
	movq	%rax, %rdi
	movq	(%rax&#41;, %rax
	movq	-24&#40;%rax&#41;, %rax
	movq	240&#40;%rdi,%rax&#41;, %rbx
	testq	%rbx, %rbx
	je	.L23
	cmpb	$0, 56&#40;%rbx&#41;
	jne	.L24
	movq	%rbx, %rcx
	call	_ZNKSt5ctypeIcE13_M_widen_initEv
	movq	(%rbx&#41;, %rax
	movl	$10, %edx
	movq	48&#40;%rax&#41;, %rax
	cmpq	%r13, %rax
	je	.L13
	movq	%rbx, %rcx
	call	*%rax
	movsbl	%al, %edx
	jmp	.L13
.L22&#58;
	xorl	%eax, %eax
	addq	$40, %rsp
	popq	%rbx
	popq	%rsi
	popq	%rdi
	popq	%rbp
	popq	%r12
	popq	%r13
	ret
.L23&#58;
	call	_ZSt16__throw_bad_castv
	nop
	.seh_endproc
	.p2align 4,,15
	.def	_GLOBAL__sub_I_arrdat;	.scl	3;	.type	32;	.endef
	.seh_proc	_GLOBAL__sub_I_arrdat
_GLOBAL__sub_I_arrdat&#58;
.LFB1976&#58;
	subq	$40, %rsp
	.seh_stackalloc	40
	.seh_endprologue
	leaq	_ZStL8__ioinit&#40;%rip&#41;, %rcx
	call	_ZNSt8ios_base4InitC1Ev
	leaq	__tcf_0&#40;%rip&#41;, %rcx
	addq	$40, %rsp
	jmp	atexit
	.seh_endproc
	.section	.ctors,"w"
	.align 8
	.quad	_GLOBAL__sub_I_arrdat
	.globl	arrdat
	.data
	.align 32
arrdat&#58;
	.long	9
	.long	6
	.long	23
	.long	4
	.long	5
	.long	6
	.long	7
	.long	11
	.long	2
	.long	3
	.long	1
	.long	5
	.long	9
	.long	11
	.long	0
	.long	13
	.long	-8
	.long	3
	.long	4
	.long	5
	.long	6
	.long	3
	.long	2
	.long	1
.lcomm _ZStL8__ioinit,1,1
	.ident	"GCC&#58; &#40;Rev2, Built by MSYS2 project&#41; 6.3.0"
	.def	_ZNSt8ios_base4InitD1Ev;	.scl	2;	.type	32;	.endef
	.def	_ZNSo3putEc;	.scl	2;	.type	32;	.endef
	.def	_ZNSo5flushEv;	.scl	2;	.type	32;	.endef
	.def	_ZNSolsEi;	.scl	2;	.type	32;	.endef
	.def	_ZNKSt5ctypeIcE13_M_widen_initEv;	.scl	2;	.type	32;	.endef
	.def	_ZSt16__throw_bad_castv;	.scl	2;	.type	32;	.endef
	.def	_ZNSt8ios_base4InitC1Ev;	.scl	2;	.type	32;	.endef
	.def	atexit;	.scl	2;	.type	32;	.endef
	.section	.rdata$.refptr._ZSt4cout, "dr"
	.globl	.refptr._ZSt4cout
	.linkonce	discard
.refptr._ZSt4cout&#58;
	.quad	_ZSt4cout
Taking ideas is not a vice, it is a virtue. We have another word for this. It is called learning.
But sharing ideas is an even greater virtue. We have another word for this. It is called teaching.
Dann Corbit
Posts: 12534
Joined: Wed Mar 08, 2006 8:57 pm
Location: Redmond, WA USA

Re: Sorting algorithms

Post by Dann Corbit »

Oops, that was the assembly listing for the original. Still holds true for the template version though:

Code: Select all

	.file	"snetep.cpp"
	.section	.text$_ZNKSt5ctypeIcE8do_widenEc,"x"
	.linkonce discard
	.align 2
	.p2align 4,,15
	.globl	_ZNKSt5ctypeIcE8do_widenEc
	.def	_ZNKSt5ctypeIcE8do_widenEc;	.scl	2;	.type	32;	.endef
	.seh_proc	_ZNKSt5ctypeIcE8do_widenEc
_ZNKSt5ctypeIcE8do_widenEc&#58;
.LFB1294&#58;
	.seh_endprologue
	movl	%edx, %eax
	ret
	.seh_endproc
	.text
	.p2align 4,,15
	.def	__tcf_0;	.scl	3;	.type	32;	.endef
	.seh_proc	__tcf_0
__tcf_0&#58;
.LFB1981&#58;
	.seh_endprologue
	leaq	_ZStL8__ioinit&#40;%rip&#41;, %rcx
	jmp	_ZNSt8ios_base4InitD1Ev
	.seh_endproc
	.def	__main;	.scl	2;	.type	32;	.endef
	.section	.text.startup,"x"
	.p2align 4,,15
	.globl	main
	.def	main;	.scl	2;	.type	32;	.endef
	.seh_proc	main
main&#58;
.LFB1538&#58;
	pushq	%r13
	.seh_pushreg	%r13
	pushq	%r12
	.seh_pushreg	%r12
	pushq	%rbp
	.seh_pushreg	%rbp
	pushq	%rdi
	.seh_pushreg	%rdi
	pushq	%rsi
	.seh_pushreg	%rsi
	pushq	%rbx
	.seh_pushreg	%rbx
	subq	$40, %rsp
	.seh_stackalloc	40
	.seh_endprologue
	call	__main
	movl	4+arrdat&#40;%rip&#41;, %ecx
	movl	arrdat&#40;%rip&#41;, %eax
	movl	8+arrdat&#40;%rip&#41;, %r8d
	movl	12+arrdat&#40;%rip&#41;, %r9d
	movl	16+arrdat&#40;%rip&#41;, %r10d
	movl	20+arrdat&#40;%rip&#41;, %r11d
	cmpl	%ecx, %eax
	movl	%ecx, %edx
	movl	24+arrdat&#40;%rip&#41;, %ebx
	cmovle	%eax, %edx
	xorl	%ecx, %eax
	movl	%r8d, %ecx
	xorl	%edx, %eax
	movl	28+arrdat&#40;%rip&#41;, %esi
	movl	32+arrdat&#40;%rip&#41;, %edi
	cmpl	%r8d, %eax
	movl	36+arrdat&#40;%rip&#41;, %ebp
	cmovle	%eax, %ecx
	xorl	%r8d, %eax
	movl	%r9d, %r8d
	xorl	%ecx, %eax
	cmpl	%r9d, %eax
	cmovle	%eax, %r8d
	xorl	%r9d, %eax
	movl	%r10d, %r9d
	xorl	%r8d, %eax
	movl	%r8d, %r12d
	cmpl	%r10d, %eax
	cmovle	%eax, %r9d
	xorl	%r10d, %eax
	movl	%r11d, %r10d
	xorl	%r9d, %eax
	cmpl	%r11d, %eax
	cmovle	%eax, %r10d
	xorl	%r11d, %eax
	movl	%ebx, %r11d
	xorl	%r10d, %eax
	cmpl	%ebx, %eax
	cmovle	%eax, %r11d
	xorl	%ebx, %eax
	movl	%esi, %ebx
	xorl	%r11d, %eax
	cmpl	%esi, %eax
	cmovle	%eax, %ebx
	xorl	%esi, %eax
	movl	%edi, %esi
	xorl	%ebx, %eax
	cmpl	%edi, %eax
	cmovle	%eax, %esi
	xorl	%edi, %eax
	movl	%ebp, %edi
	xorl	%esi, %eax
	cmpl	%ebp, %eax
	cmovle	%eax, %edi
	xorl	%ebp, %eax
	movl	%ecx, %ebp
	xorl	%edi, %eax
	cmpl	%ecx, %edx
	cmovle	%edx, %ebp
	xorl	%ecx, %edx
	movl	%r9d, %ecx
	xorl	%ebp, %edx
	movl	%eax, 36+arrdat&#40;%rip&#41;
	cmpl	%r8d, %edx
	cmovle	%edx, %r12d
	xorl	%r8d, %edx
	movl	%r10d, %r8d
	xorl	%r12d, %edx
	cmpl	%r9d, %edx
	cmovle	%edx, %ecx
	xorl	%r9d, %edx
	movl	%r11d, %r9d
	xorl	%ecx, %edx
	cmpl	%r10d, %edx
	cmovle	%edx, %r8d
	xorl	%r10d, %edx
	movl	%ebx, %r10d
	xorl	%r8d, %edx
	cmpl	%r11d, %edx
	cmovle	%edx, %r9d
	xorl	%r11d, %edx
	movl	%edi, %r11d
	xorl	%r9d, %edx
	cmpl	%ebx, %edx
	movl	%edx, %eax
	cmovle	%edx, %r10d
	xorl	%ebx, %eax
	movl	%esi, %edx
	xorl	%r10d, %eax
	movl	%ebp, %ebx
	cmpl	%esi, %eax
	cmovle	%eax, %edx
	xorl	%esi, %eax
	movl	%ecx, %esi
	xorl	%edx, %eax
	cmpl	%edi, %eax
	cmovle	%eax, %r11d
	xorl	%edi, %eax
	movl	%r8d, %edi
	xorl	%r11d, %eax
	cmpl	%ebp, %r12d
	cmovle	%r12d, %ebx
	xorl	%r12d, %ebp
	movl	%eax, 32+arrdat&#40;%rip&#41;
	xorl	%ebx, %ebp
	cmpl	%ecx, %ebp
	cmovle	%ebp, %esi
	xorl	%ebp, %ecx
	xorl	%esi, %ecx
	cmpl	%r8d, %ecx
	cmovle	%ecx, %edi
	xorl	%ecx, %r8d
	movl	%r9d, %ecx
	xorl	%edi, %r8d
	cmpl	%r9d, %r8d
	cmovle	%r8d, %ecx
	xorl	%r8d, %r9d
	movl	%r10d, %r8d
	xorl	%ecx, %r9d
	cmpl	%r10d, %r9d
	cmovle	%r9d, %r8d
	xorl	%r9d, %r10d
	movl	%edx, %r9d
	xorl	%r8d, %r10d
	cmpl	%edx, %r10d
	cmovle	%r10d, %r9d
	xorl	%edx, %r10d
	movl	%r11d, %edx
	movl	%r10d, %eax
	movl	%ebx, %r10d
	xorl	%r9d, %eax
	cmpl	%r11d, %eax
	cmovle	%eax, %edx
	xorl	%r11d, %eax
	movl	%edi, %r11d
	xorl	%edx, %eax
	cmpl	%ebx, %esi
	cmovle	%esi, %r10d
	xorl	%esi, %ebx
	movl	%eax, 28+arrdat&#40;%rip&#41;
	xorl	%r10d, %ebx
	movl	%r8d, %esi
	cmpl	%edi, %ebx
	cmovle	%ebx, %r11d
	xorl	%ebx, %edi
	movl	%ecx, %ebx
	xorl	%r11d, %edi
	cmpl	%ecx, %edi
	cmovle	%edi, %ebx
	xorl	%edi, %ecx
	xorl	%ebx, %ecx
	movl	%ebx, %edi
	cmpl	%r8d, %ecx
	movl	%ecx, %eax
	cmovle	%ecx, %esi
	xorl	%r8d, %eax
	movl	%r9d, %ecx
	xorl	%esi, %eax
	movl	%edx, %r8d
	cmpl	%r9d, %eax
	cmovle	%eax, %ecx
	xorl	%r9d, %eax
	movl	%r10d, %r9d
	xorl	%ecx, %eax
	cmpl	%edx, %eax
	cmovle	%eax, %r8d
	xorl	%edx, %eax
	xorl	%r8d, %eax
	cmpl	%r10d, %r11d
	cmovle	%r11d, %r9d
	xorl	%r11d, %r10d
	movl	%esi, %r11d
	xorl	%r9d, %r10d
	movl	%eax, 24+arrdat&#40;%rip&#41;
	cmpl	%ebx, %r10d
	cmovle	%r10d, %edi
	xorl	%r10d, %ebx
	movl	%ecx, %r10d
	xorl	%edi, %ebx
	cmpl	%esi, %ebx
	cmovle	%ebx, %r11d
	xorl	%esi, %ebx
	xorl	%r11d, %ebx
	cmpl	%ecx, %ebx
	movl	%ebx, %eax
	cmovle	%ebx, %r10d
	xorl	%ecx, %eax
	xorl	%r10d, %eax
	cmpl	%eax, %r8d
	movl	%eax, %ebx
	cmovle	%r8d, %ebx
	xorl	%r8d, %eax
	movl	%edi, %r8d
	xorl	%ebx, %eax
	cmpl	%edi, %r9d
	cmovle	%r9d, %r8d
	xorl	%edi, %r9d
	movl	%eax, 20+arrdat&#40;%rip&#41;
	xorl	%r8d, %r9d
	movl	%r11d, %eax
	cmpl	%r11d, %r9d
	cmovle	%r9d, %eax
	xorl	%r11d, %r9d
	movl	%r9d, %edx
	xorl	%eax, %edx
	cmpl	%edx, %r10d
	movl	%edx, %r11d
	cmovle	%r10d, %r11d
	xorl	%r10d, %edx
	leaq	44+arrdat&#40;%rip&#41;, %r10
	xorl	%r11d, %edx
	movl	%r11d, %r9d
	cmpl	%edx, %ebx
	movl	%edx, %ecx
	cmovle	%ebx, %ecx
	xorl	%ebx, %edx
	xorl	%ecx, %edx
	cmpl	%r8d, %eax
	movl	%edx, 16+arrdat&#40;%rip&#41;
	movl	%r8d, %edx
	cmovle	%eax, %edx
	xorl	%r8d, %eax
	xorl	%edx, %eax
	cmpl	%r11d, %eax
	cmovle	%eax, %r9d
	xorl	%r11d, %eax
	leaq	92+arrdat&#40;%rip&#41;, %r11
	xorl	%r9d, %eax
	cmpl	%eax, %ecx
	movl	%eax, %r8d
	cmovle	%ecx, %r8d
	xorl	%ecx, %eax
	movl	%r9d, %ecx
	xorl	%r8d, %eax
	cmpl	%r9d, %edx
	cmovle	%edx, %ecx
	xorl	%r9d, %edx
	movl	%eax, 12+arrdat&#40;%rip&#41;
	xorl	%ecx, %edx
	movl	%r8d, %eax
	leaq	40+arrdat&#40;%rip&#41;, %r9
	cmpl	%r8d, %edx
	cmovle	%edx, %eax
	xorl	%r8d, %edx
	leaq	arrdat&#40;%rip&#41;, %r8
	xorl	%eax, %edx
	cmpl	%ecx, %eax
	movl	%edx, 8+arrdat&#40;%rip&#41;
	movl	%ecx, %edx
	cmovle	%eax, %edx
	xorl	%ecx, %eax
	xorl	%edx, %eax
	cmpq	%r8, %r9
	movl	%edx, arrdat&#40;%rip&#41;
	movl	%eax, 4+arrdat&#40;%rip&#41;
	movq	%r9, %rax
	movl	(%r9&#41;, %ecx
	je	.L5
	.p2align 4,,10
.L21&#58;
	movl	-8&#40;%r10&#41;, %edx
	cmpl	%ecx, %edx
	jg	.L8
	jmp	.L6
	.p2align 4,,10
.L9&#58;
	movl	-4&#40;%rax&#41;, %edx
	cmpl	%edx, %ecx
	jge	.L6
.L8&#58;
	movl	%edx, (%rax&#41;
	subq	$4, %rax
	cmpq	%r8, %rax
	jne	.L9
.L6&#58;
	cmpq	%r11, %r10
	movl	%ecx, (%rax&#41;
	jnb	.L20
.L10&#58;
	addq	$4, %r9
	addq	$4, %r10
	movl	(%r9&#41;, %ecx
	cmpq	%r8, %r9
	movq	%r9, %rax
	jne	.L21
.L5&#58;
	movl	%ecx, (%r9&#41;
	jmp	.L10
.L20&#58;
	leaq	arrdat&#40;%rip&#41;, %rsi
	leaq	96+arrdat&#40;%rip&#41;, %r12
	movq	.refptr._ZSt4cout&#40;%rip&#41;, %rbp
	leaq	_ZNKSt5ctypeIcE8do_widenEc&#40;%rip&#41;, %r13
	jmp	.L14
	.p2align 4,,10
.L24&#58;
	movsbl	67&#40;%rbx&#41;, %edx
.L13&#58;
	movq	%rdi, %rcx
	addq	$4, %rsi
	call	_ZNSo3putEc
	movq	%rax, %rcx
	call	_ZNSo5flushEv
	cmpq	%rsi, %r12
	je	.L22
.L14&#58;
	movl	(%rsi&#41;, %edx
	movq	%rbp, %rcx
	call	_ZNSolsEi
	movq	%rax, %rdi
	movq	(%rax&#41;, %rax
	movq	-24&#40;%rax&#41;, %rax
	movq	240&#40;%rdi,%rax&#41;, %rbx
	testq	%rbx, %rbx
	je	.L23
	cmpb	$0, 56&#40;%rbx&#41;
	jne	.L24
	movq	%rbx, %rcx
	call	_ZNKSt5ctypeIcE13_M_widen_initEv
	movq	(%rbx&#41;, %rax
	movl	$10, %edx
	movq	48&#40;%rax&#41;, %rax
	cmpq	%r13, %rax
	je	.L13
	movq	%rbx, %rcx
	call	*%rax
	movsbl	%al, %edx
	jmp	.L13
.L22&#58;
	xorl	%eax, %eax
	addq	$40, %rsp
	popq	%rbx
	popq	%rsi
	popq	%rdi
	popq	%rbp
	popq	%r12
	popq	%r13
	ret
.L23&#58;
	call	_ZSt16__throw_bad_castv
	nop
	.seh_endproc
	.p2align 4,,15
	.def	_GLOBAL__sub_I_arrdat;	.scl	3;	.type	32;	.endef
	.seh_proc	_GLOBAL__sub_I_arrdat
_GLOBAL__sub_I_arrdat&#58;
.LFB1982&#58;
	subq	$40, %rsp
	.seh_stackalloc	40
	.seh_endprologue
	leaq	_ZStL8__ioinit&#40;%rip&#41;, %rcx
	call	_ZNSt8ios_base4InitC1Ev
	leaq	__tcf_0&#40;%rip&#41;, %rcx
	addq	$40, %rsp
	jmp	atexit
	.seh_endproc
	.section	.ctors,"w"
	.align 8
	.quad	_GLOBAL__sub_I_arrdat
	.globl	arrdat
	.data
	.align 32
arrdat&#58;
	.long	9
	.long	6
	.long	23
	.long	4
	.long	5
	.long	6
	.long	7
	.long	11
	.long	2
	.long	3
	.long	1
	.long	5
	.long	9
	.long	11
	.long	0
	.long	13
	.long	-8
	.long	3
	.long	4
	.long	5
	.long	6
	.long	3
	.long	2
	.long	1
.lcomm _ZStL8__ioinit,1,1
	.ident	"GCC&#58; &#40;Rev2, Built by MSYS2 project&#41; 6.3.0"
	.def	_ZNSt8ios_base4InitD1Ev;	.scl	2;	.type	32;	.endef
	.def	_ZNSo3putEc;	.scl	2;	.type	32;	.endef
	.def	_ZNSo5flushEv;	.scl	2;	.type	32;	.endef
	.def	_ZNSolsEi;	.scl	2;	.type	32;	.endef
	.def	_ZNKSt5ctypeIcE13_M_widen_initEv;	.scl	2;	.type	32;	.endef
	.def	_ZSt16__throw_bad_castv;	.scl	2;	.type	32;	.endef
	.def	_ZNSt8ios_base4InitC1Ev;	.scl	2;	.type	32;	.endef
	.def	atexit;	.scl	2;	.type	32;	.endef
	.section	.rdata$.refptr._ZSt4cout, "dr"
	.globl	.refptr._ZSt4cout
	.linkonce	discard
.refptr._ZSt4cout&#58;
	.quad	_ZSt4cout
Taking ideas is not a vice, it is a virtue. We have another word for this. It is called learning.
But sharing ideas is an even greater virtue. We have another word for this. It is called teaching.
AlvaroBegue
Posts: 931
Joined: Tue Mar 09, 2010 3:46 pm
Location: New York
Full name: Álvaro Begué (RuyDos)

Re: Sorting algorithms

Post by AlvaroBegue »

You could increase readability by introducing a function like this:

Code: Select all

template <typename T>
void sort_pair&#40;T &a, T &b&#41; &#123;
  T mask = (-&#40;a > b&#41;) & &#40;a ^ b&#41;;
  a ^= mask;
  b ^= mask;
&#125;
This is the first implementation that came to mind, which is something I thought of before CPUs had conditional mov instructions. Perhaps other implementations are better. But the point is that you don't need macros or very repetitive code.
User avatar
hgm
Posts: 27768
Joined: Fri Mar 10, 2006 10:06 am
Location: Amsterdam
Full name: H G Muller

Re: Sorting algorithms

Post by hgm »

I think it is awful. I would be surprised if it is anywhere near as fast as

Code: Select all

void
Sort &#40;Move *moves, unsigned char *key, int nrMoves&#41;
&#123;
  unsigned char head&#91;256&#93;;
  unsigned char next&#91;MAXMOVES&#93;;
  Move temp&#91;MAXMOVES&#93;;
  int i, used = 0;

  for&#40;i=0; i<nrMoves; i++) &#123; // disperse
    int k = key&#91;i&#93;;
    int bit = 1 << k;
    temp&#91;i&#93; = moves&#91;i&#93;;
    next&#91;i&#93; = &#40;bit & used ? head&#91;k&#93; &#58; 0&#41;; // cmov
    head&#91;k&#93; = i;
    used |= bit;
  &#125; // one mis-predict at loop end

  i = 0;
  while&#40;used&#41; &#123; // collect
    int b = BSF&#40;used&#41;; // next occupied bin
    int j = head&#91;b&#93;;
    do &#123;
      moves&#91;i++&#93; = temp&#91;j&#93;;
    &#125; while&#40;&#40;j = next&#91;j&#93;)); // rarely taken branch, as most bins have 1 move
    used -= 1 << b;
  &#125;
&#125; // 1 mis-predict at end
Except perhaps for 1 or 2 elements.
Dann Corbit
Posts: 12534
Joined: Wed Mar 08, 2006 8:57 pm
Location: Redmond, WA USA

Re: Sorting algorithms

Post by Dann Corbit »

hgm wrote:I think it is awful. I would be surprised if it is anywhere near as fast as

Code: Select all

void
Sort &#40;Move *moves, unsigned char *key, int nrMoves&#41;
&#123;
  unsigned char head&#91;256&#93;;
  unsigned char next&#91;MAXMOVES&#93;;
  Move temp&#91;MAXMOVES&#93;;
  int i, used = 0;

  for&#40;i=0; i<nrMoves; i++) &#123; // disperse
    int k = key&#91;i&#93;;
    int bit = 1 << k;
    temp&#91;i&#93; = moves&#91;i&#93;;
    next&#91;i&#93; = &#40;bit & used ? head&#91;k&#93; &#58; 0&#41;; // cmov
    head&#91;k&#93; = i;
    used |= bit;
  &#125; // one mis-predict at loop end

  i = 0;
  while&#40;used&#41; &#123; // collect
    int b = BSF&#40;used&#41;; // next occupied bin
    int j = head&#91;b&#93;;
    do &#123;
      moves&#91;i++&#93; = temp&#91;j&#93;;
    &#125; while&#40;&#40;j = next&#91;j&#93;)); // rarely taken branch, as most bins have 1 move
    used -= 1 << b;
  &#125;
&#125; // 1 mis-predict at end
Except perhaps for 1 or 2 elements.
Yours might be faster for move sorting, but the other routine was general purpose.

Your routine (for instance) assumes that the items are unique.

There was a fencepost error in my driver, since I did not notice that his loop stopped before the last element.

The end parameter should have been &arrdat[adim] rather than &arrdat[adim-1].

Code: Select all

int main&#40; void )
&#123;
    static const size_t adim = sizeof arrdat / sizeof arrdat&#91;0&#93;;
    size_t index;
    stable_sorting_network <int> ( &arrdat&#91;0&#93;, &arrdat&#91;adim&#93; );
    for ( index = 0; index < adim; index++ )
        std&#58;&#58;cout << arrdat&#91;index&#93; << std&#58;&#58;endl;
    return 0;
&#125;
Taking ideas is not a vice, it is a virtue. We have another word for this. It is called learning.
But sharing ideas is an even greater virtue. We have another word for this. It is called teaching.
User avatar
hgm
Posts: 27768
Joined: Fri Mar 10, 2006 10:06 am
Location: Amsterdam
Full name: H G Muller

Re: Sorting algorithms

Post by hgm »

Dann Corbit wrote:Your routine (for instance) assumes that the items are unique.
No, it doesn't. This is why I needed linked lists, to have an arbitrary number of moves with the same key. If the keys were guaranteed to be unique, you could just hash the moves by key to a 256-element array, and then pack that array by squeezing out the unused entries.

It still assumed maximally different keys, though. (Or 64 if 'used' would be made a 64-bit type.) To allow 256 different keys the set that indicates which bins are in use (which allows fast skipping of the unused bins by bit extraction) would have to be divided over multiple machine words, requiring the key to be split into an index into an array used[4], and a bit number 0-63.

And the design is not even optimal, because it was written to sort an existing array in-place. Which then requires making of a copy, and then write it back in sorted order. Which is a stupid thing to do, as you could have generated the moves in a scratch array, and copy it in sorted order to the move stack. Saving you half the read and write accesses on the move data. There also is no need to actually store the keys; the iterations of the first loop could simply be moved to the move generation, using the calculated sort key only as index, never storing it.
petero2
Posts: 683
Joined: Mon Apr 19, 2010 7:07 pm
Location: Sweden
Full name: Peter Osterlund

Re: Sorting algorithms

Post by petero2 »

Kempelen wrote:Today I was thinking on what algorithm to use for sorting moves, that be the faster. Currently I am using "selection sort" as it was the first that comes to my mind when writting my engine, but now I trying to investigating what is the best.

Any orientation in this area will be wellcome.
In texel I have not found anything better than "on demand" selection sort. That is, whenever a new move is needed I iterate over all remaining moves and pick the best one. This has the advantage that in CUT nodes you often only have to select one move, so a single pass over the move list is enough.

I don't use a staged move generator in texel, so the average move list size is around 35. I have tried using a heap data structure since it also supports "on demand" sorting, but it was not a win. One trick I use is to not order any moves after the LMP move count limit has been exceeded. The idea being that if you have tried enough moves to start considering the LMP condition, the remaining moves are probably not good, so spending time trying to order them is probably wasted.

I made a 2D histogram searching an opening position (r1bq1rk1/2p1bppp/p1np1n2/1p2p3/4P3/1BP2N2/PP1P1PPP/RNBQR1K1 w - - 1 9) to depth 22.

Image

The horizontal axis is the size of the move list and the depth axis is the number of moves "picked" by the on demand selection sort.

It can be seen that for most nodes only very few moves are picked. The ridges at 3,6,12,24 correspond to the LMP move count limit for depth=1,2,3,4 respectively. The diagonal ridge corresponds to ALL nodes where LMP is not used.

I have not verified this, but I think the peak at move list size 4 corresponds to positions where the side to move is in check and the peak at 36 corresponds to not in check positions.

Raw data for the plot:

Code: Select all

13545 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
441052 107205 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1377911 31102 197744 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1424946 58336 5958 167916 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
648143 46074 5210 651 101003 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
288390 22517 5889 765 357 52606 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
169926 10224 3444 605 344 268 23993 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
87999 4907 1989 281 146 101 33 10933 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
43774 2596 892 113 71 45 12 13 4243 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
20873 862 263 42 13 13 4 1 1 1323 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
7769 265 64 21 7 7 1 3 1 1 524 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
2717 77 29 1 2 1 3 1 1 0 0 230 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1112 34 15 2 1 5 0 1 0 0 0 3 105 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
607 20 7 1 0 11 1 0 0 0 0 10 0 166 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
322 47 7 1 3 22 1 0 0 2 0 18 0 0 358 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
703 88 44 5 6 51 3 2 2 0 0 32 0 0 0 740 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1504 173 60 14 8 111 2 0 1 0 1 82 0 0 0 0 1443 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
3680 453 133 50 26 310 8 4 1 2 1 203 2 0 0 0 0 3482 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
8436 899 265 72 50 659 20 9 10 5 9 387 2 1 0 2 0 0 7097 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
17729 1958 469 110 85 1144 12 22 16 18 12 773 3 1 4 1 2 0 3 14048 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
33580 3574 1102 232 175 2071 44 29 35 26 16 1566 6 7 4 4 3 4 3 5 25306 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
62930 6425 1809 445 270 3934 94 77 50 54 40 2964 15 14 10 3 6 6 7 4 9 44447 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
122530 11968 3371 832 534 6974 165 97 90 79 69 5693 20 14 22 14 15 16 8 6 12 9 78178 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
215945 20311 5702 1388 897 11494 240 231 178 125 97 9413 42 32 35 28 23 21 18 16 9 21 26 124725 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
334603 31666 8775 2266 1395 16715 400 348 249 187 162 14535 73 62 51 43 33 38 20 22 25 12 16 9904 174337 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
514099 48012 13262 3562 2011 23622 552 424 327 292 238 20616 85 91 67 51 51 46 35 34 27 25 14 14213 28 236957 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
762175 70155 19416 5188 2847 32236 823 653 539 483 339 28576 159 130 102 94 73 66 56 56 44 23 28 19842 17 55 311498 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1052251 91714 26760 6739 4115 41303 1128 910 667 609 462 37254 204 165 140 110 100 89 68 64 54 36 43 25893 11 24 61 388998 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1390613 118143 34179 9026 5123 49968 1339 1123 899 786 621 46319 258 233 196 163 132 112 122 83 83 67 53 31414 22 17 34 98 458404 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1617231 139911 40172 10390 5792 55290 1600 1268 1090 840 714 50731 313 253 238 186 157 134 137 105 90 76 84 34673 17 17 21 30 112 500011 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1819651 155725 45130 11743 6491 60882 1914 1486 1203 1027 861 56865 305 292 250 217 204 175 142 137 107 114 78 37527 33 32 31 31 40 148 542530 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
2017854 173254 50185 12847 7144 65507 2012 1660 1287 1067 937 61548 397 324 301 261 184 176 176 178 130 127 109 39490 43 20 27 26 32 48 164 580255 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
2188176 187751 55236 14507 7692 68876 2174 1739 1473 1164 1034 65473 387 382 312 297 263 220 176 168 147 138 117 41161 49 45 39 24 21 36 63 229 601253 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
2337259 200880 60821 15803 8326 70885 2298 1845 1489 1308 1073 66687 412 400 349 326 271 265 197 216 177 144 139 41362 58 53 46 38 33 25 47 97 237 604597 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
2452367 206548 61708 16470 8619 72014 2396 1835 1470 1287 1125 67691 521 409 323 310 299 253 256 213 192 177 146 40596 64 55 44 47 32 35 28 51 117 316 595336 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
2544479 213469 64459 16989 8899 73250 2456 2000 1653 1324 1136 67667 504 433 359 332 288 274 255 208 182 192 143 40351 77 52 64 52 33 35 31 35 48 156 383 578453 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
2491686 210810 63511 16882 8660 69680 2409 1962 1579 1364 1163 65010 479 420 352 301 285 264 244 203 188 180 187 38224 71 68 48 48 35 49 26 32 37 60 156 384 545487 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
2395628 204515 61737 16473 8614 66246 2401 1907 1575 1323 1197 60968 470 413 367 354 259 285 233 217 207 174 171 35030 61 65 87 52 48 32 42 30 37 32 80 180 431 498580 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
2221290 189232 58665 15794 8326 60238 2299 1791 1449 1306 1060 55408 456 387 351 312 279 289 223 217 186 160 173 31352 83 57 56 55 38 46 37 33 29 27 59 108 224 433 441266 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
2013521 172332 53542 14639 7455 53913 2054 1622 1367 1167 1020 49202 431 395 339 290 254 226 184 167 162 154 131 27233 87 62 60 48 49 34 39 26 24 27 29 65 121 219 461 386604 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1786795 152702 48044 13358 6885 48133 1896 1516 1278 1021 928 43688 377 326 297 260 243 232 188 180 137 149 122 23564 55 65 47 52 39 30 30 34 27 30 25 35 58 125 214 458 331923 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1551343 131645 42241 12114 6079 41413 1689 1309 1069 950 820 37134 318 284 300 229 248 192 162 193 142 128 121 19857 56 54 43 46 39 33 36 23 31 26 21 23 40 55 107 187 440 281487 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1337700 117114 37260 10675 5497 35737 1481 1206 963 803 714 31647 266 271 213 216 182 170 156 145 124 124 122 16421 45 48 39 37 36 34 27 28 24 22 25 14 16 34 69 110 201 431 234298 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1142794 99992 32144 9298 4739 30043 1282 997 807 706 604 26245 262 216 199 185 176 135 140 122 125 102 102 13533 44 42 34 30 33 31 25 23 17 17 18 12 9 25 45 67 96 175 383 191818 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
934773 82034 27145 7818 4026 24906 1120 832 737 603 489 21900 232 173 148 123 143 129 111 120 90 91 89 10968 36 26 35 31 24 32 19 20 23 14 18 13 19 8 9 37 95 101 194 352 154534 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
745716 65308 22224 6608 3374 20209 941 692 594 495 401 17541 159 163 150 127 119 101 99 105 79 65 74 8391 27 36 25 25 23 16 24 16 14 15 17 3 10 10 10 16 50 92 81 161 278 123319 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
592908 52693 18329 5222 2749 16436 749 566 457 373 328 14168 140 133 119 120 102 82 85 70 54 55 62 6867 28 24 30 23 16 15 17 10 11 16 6 16 6 8 11 10 12 40 73 73 140 235 96484 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
457553 41391 14372 4269 2274 12899 563 453 372 302 273 10870 99 87 73 82 73 71 48 64 53 46 45 5266 18 25 17 20 19 11 19 16 18 16 9 4 9 3 7 12 5 12 29 53 71 111 229 73953 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
350138 31682 11008 3303 1713 10048 423 363 314 271 243 8157 80 70 68 63 56 62 48 52 30 42 33 3957 21 12 13 13 14 5 14 14 14 4 12 3 7 8 8 7 4 5 7 29 51 58 101 178 55101 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
259494 23692 8519 2584 1359 7439 316 250 234 188 181 6068 64 69 56 57 42 47 37 36 30 34 30 2775 19 18 13 11 10 6 10 9 8 4 6 5 8 7 3 6 5 2 3 3 20 35 50 96 149 40668 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
191950 17508 6314 1967 1020 5606 256 192 174 142 136 4436 49 37 43 28 36 34 28 24 22 16 24 1992 13 20 13 13 8 7 6 3 8 4 2 7 4 3 3 7 5 2 4 11 8 15 23 34 77 103 29716 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
140596 12882 4529 1507 760 4115 189 142 134 93 75 3232 40 29 30 31 26 16 19 27 14 14 13 1470 6 4 1 10 6 7 5 6 5 1 3 4 6 3 3 5 0 0 2 0 4 9 27 12 28 53 78 21335 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
100381 9179 3347 1065 512 3090 125 108 80 66 53 2325 25 21 25 13 19 17 16 13 13 10 11 1048 5 6 3 4 1 1 4 0 5 3 2 1 4 3 2 3 1 1 4 2 1 2 4 18 15 37 62 69 15258 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
72065 6806 2487 757 410 2158 106 75 62 46 40 1653 21 18 17 14 7 12 8 9 11 7 6 730 5 3 1 6 1 2 1 5 3 3 1 1 4 0 1 2 1 2 0 0 0 0 1 4 3 10 20 43 61 10553 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
51064 4841 1677 554 317 1468 69 54 45 33 36 1064 14 12 9 12 12 9 11 9 4 3 5 453 1 0 2 4 2 3 2 1 1 1 2 1 0 0 1 2 2 2 0 1 1 0 0 0 1 2 10 13 33 42 7360 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
34257 3200 1155 312 202 1076 54 42 31 23 14 802 7 6 9 12 6 7 1 4 5 7 1 339 2 0 2 0 0 0 3 3 1 0 1 0 0 1 0 0 2 0 0 1 0 0 2 0 1 1 8 6 25 25 40 4934 0 0 0 0 0 0 0 0 0 0 0 0 0 0
22852 2186 768 269 133 660 31 30 16 20 15 489 4 9 5 5 7 9 2 5 4 3 1 214 1 4 1 1 1 0 1 1 1 0 0 0 1 0 1 1 0 0 0 0 0 1 0 0 0 0 2 2 7 15 22 19 3088 0 0 0 0 0 0 0 0 0 0 0 0 0
15190 1449 552 191 113 424 22 20 13 13 13 318 6 6 7 3 3 1 1 1 3 0 3 144 2 0 1 0 0 1 0 0 1 1 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 4 2 5 3 10 10 2057 0 0 0 0 0 0 0 0 0 0 0 0
9477 954 354 132 65 278 14 15 9 5 4 218 0 2 2 2 0 1 2 2 0 1 1 74 0 0 1 2 1 0 1 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 3 0 1 8 6 9 1312 0 0 0 0 0 0 0 0 0 0 0
5655 602 222 74 43 178 11 9 6 3 4 119 2 3 2 0 1 3 0 0 0 1 0 55 0 1 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 3 2 2 3 774 0 0 0 0 0 0 0 0 0 0
3495 356 119 49 35 111 6 5 5 5 5 83 1 2 2 2 0 0 0 1 1 0 0 35 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 3 6 525 0 0 0 0 0 0 0 0 0
1944 202 68 39 24 77 2 1 3 1 2 54 0 0 1 1 0 0 0 1 0 0 1 14 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 2 0 1 315 0 0 0 0 0 0 0 0
1136 111 57 20 12 43 2 1 1 2 0 26 1 0 1 0 0 0 0 0 0 0 0 7 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 1 0 2 1 168 0 0 0 0 0 0 0
577 75 18 13 4 24 0 0 0 0 0 19 1 0 0 0 0 1 0 0 0 0 0 6 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 87 0 0 0 0 0 0
295 33 13 10 4 16 1 2 0 0 0 11 0 0 0 0 0 0 1 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 59 0 0 0 0 0
135 24 12 3 1 5 0 0 1 0 0 4 0 0 1 0 1 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 30 0 0 0 0
58 7 5 1 1 1 0 0 0 1 0 2 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 11 0 0 0
20 3 3 2 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 12 0 0
13 2 1 1 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 3 2
User avatar
hgm
Posts: 27768
Joined: Fri Mar 10, 2006 10:06 am
Location: Amsterdam
Full name: H G Muller

Re: Sorting algorithms

Post by hgm »

Very nice graph. In my experience it is worthwile to take such statistics as a function of remaining depth. Otherwise it is completely dominated by the d=1 nodes, while the statistics in deeper nodes might be completely different. (E.g. because the availability of a hash move is much more common there.)

It seems that when the first move does not cut, it is most likely you eventually will pick all moves. This makes it a bit surprising that the 'on-demand' sorting has any benefits, and that more efficient sorting algorithms (incompatible with on-demand) would not perform better.
lauriet
Posts: 199
Joined: Sun Nov 03, 2013 9:32 am

Re: Sorting algorithms

Post by lauriet »

My program does the following:

Generate Moves;
Assign the move values (PV, TT, Killers etc)
Quick Sort.

So based on the idea of 'dont sort if you dont have to', I mod'ed it to illiminate quicksort and just scan the move list and pick the highest scoring move for each next move.
If its a early cut node you should save time.

The result: No different to the original method ????????