Ackermann function and optimization

Have you heard of the Ackermann function?

This function is simple, but if you try to calculate it naively, soon the computational cost increases and it will never ends.

I've written the function naively, in x86 assembly language to demonstrate some optimization techniques. I could calculate up to ack(3, 11) and the stack overflowed beyond that point.

Optimizations

• Use JMP instead of CALL for tail recursions
• Use TEST + JE for macro fusion
• Use ADD / SUB instead of INC / DEC to eliminate false dependency in flag register
• Use MOV EDX, 1 instead of MOV EDX, 1 to reduce code size

    .code

ack PROC public

    ; RCX = m, RDX = n
    TEST    RCX, RCX
    JE      m_zero

    TEST    RDX, RDX
    JE      n_zero

    PUSH    RCX
    SUB     RDX, 1
    CALL    ack
    POP     RCX
    SUB     RCX, 1
    MOV     RDX, RAX
    JMP     ack

n_zero:
    MOV     EDX, 1
    SUB     RCX, 1
    JMP     ack

m_zero:
    MOV     RAX, RDX
    ADD     RAX, 1
    RET

    ack ENDP

factorial PROC public
    
    MOV     EAX, 1
    CMP     RCX, 1
    JLE     f_ret

f_loop:
    IMUL    RAX, RCX
    SUB     RCX, 1
    CMP     RCX, 1
    JNLE    f_loop

f_ret:

    RET

    factorial ENDP

    END

This program was faster than the C version below by 30%(C version was compiled with Visual C++ 2010 with /O2 option), on a Core 2 Duo processor. The factorial function was almost as fast as the C version.

int64_t factorial_c(int64_t n)
{
    int64_t r = 1;
    while(n > 1) r *= n--;
    return r;
}

int64_t ack_c(int64_t m, int64_t n)
{
    return m == 0 ? n + 1 : n == 0 ? ack_c(m - 1, 1) : ack_c(m - 1, ack_c(m, n - 1));
}

MySQL Backup Script

MySQL is one of the most popular RDBMS in the world, however, there is no out-of-box backup method. mysqldump is not sufficient when we mix InnoDB and MyISAM in one scheme.

I have written a PowerShell script to backup tables from MySQL databases, using either --single-transaction for InnoDB and --lock-tables for MyISAM tables.

Run the script from shell and you will get backup-DBNAME.sql files in your current directory for each database. This script will use table locks for MyISAM tables and transactions for InnoDB tables. Note if you are using READ-COMMITTED isolation level, backups might not be consistent between transactions. This should not matter when you are using READ-COMMITTED.

In the following example, MediaWiki is read with a table lock because it has one MyISAM table for indexing while the others are InnoDB.

I'm using this script to dump my database everyday and zipping them to store for a week. If you want to perform differential or incremental backups, you need to make use of binary logging feature of MySQL.

The following script is public-domain.

$innodb_dbs = @("bamboo","confluence","crowd","jira")
$myisam_dbs = @("mediawiki")
$backup_user = "backup"
$backup_password = "password"
$mysqldump = "C:\Program Files\MySQL\MySQL Server 5.5\bin\mysqldump.exe"
$password_option = "–password=" + $backup_password
foreach($db in $innodb_dbs){
&"$mysqldump" -u $backup_user $password_option –quick –opt –single-transaction $db > backup-$db.sql
}
foreach($db in $myisam_dbs){
&"$mysqldump" -u $backup_user $password_option –quick –opt –lock-tables $db > backup-$db.sql
}
&"$mysqldump" -u $backup_user $password_option –quick –opt –lock-tables –flush-privileges mysql > backup-mysql.sql

My new blog!

I'm starting a blog to share my interests.

Primary topics will be computers, programming, networking, and transport.

I live in Yokohama, Japan so I will also want to share things in Japan.