Life with open mind

2013年3月26日火曜日

Congrats, graduates from University of Tsukuba!

Congratulations, graduates from University of Tsukuba!
It was three years ago when I finished my master's course and started working. I moved to my current company 10 months ago. I am still learning a lot, yet far from "excellence."
Some of you may have found a job you've been looking for. Some may start working at a position which you don't believe the best. But anyway, keep on going. You will find the way to make your dream come true.

I will do my best as well :)

(This article is from Facebook)

2012年3月27日火曜日

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));
}

2012年3月26日月曜日

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