Perl性能优化之Memoize的实现原理

Perl程序可以通过Memoize模块对函数调用进行缓存，从而提升程序性能。

Memoize的基本用法如下

use Memoize;
memoize('slow_function');
slow_function(arguments);

当memoize过的函数被调用时，如果参数相同，那么只有第一次调用时会进行真正的函数调用。 其后的相同参数的调用，结果都将从内部缓存中直接返回。

memoize在Perl里面的实现原理

根据Memoize的用法，关键是需要对原本的函数进行一层包装（wrapper）。

下面的代码可以体现基本的实现原理。

sub memoize {
  my $fn = shift;

  my $name = $fn;
  my $cref = ref($fn) ? $fn : *{$name}{CODE};
  my $proto = prototype $cref;
  my $wrapper = sub {
    memoize_call($cref, @_);
  };

  print "memoize $fn to $wrapper -> $cref\n";
  *{$name} = $wrapper;
}

sub memoize_call {
  my $cref = shift;
  print "memoize_call $cref\n";
  &$cref(@_);
}

关键步骤是3点：

1. 通过*{$name}{CODE}获得原函数的引用
2. 创建匿名函数$wrapper = sub {...}，并实现对原函数的引用
3. 通过*{$name}=$wrapper将原函数的名称映射到上面的匿名函数

神奇的预先声明

比较“神奇”的一点是，memozie允许在原函数被定义之前就先被声明为memoize。

而后面的函数定义并不会改变真正被调用的是wrapper函数这一设定。

这一特点使得可以在不修改函数调用代码的情况下启用或停用相应函数的memoize。

测试代码和结果

用下面的代码进行测试

# define function before memoize

sub slow_func_1 {
  print "\@_ 1 = ".join(" , ", @_)."\n";
}

# Check function reference

print '\&slow_func_1              = '.(\&slow_func_1)."\n";
print '*{slow_func_1}{CODE}       = '.(*{slow_func_1}{CODE})."\n";
print '*{main::slow_func_1}{CODE} = '.(*{main::slow_func_1}{CODE})."\n";

# momoize function

memoize('slow_func_1');

print '\&slow_func_1              = '.(\&slow_func_1)."\n";
print '*{slow_func_1}{CODE}       = '.(*{slow_func_1}{CODE})."\n";
print '*{main::slow_func_1}{CODE} = '.(*{main::slow_func_1}{CODE})."\n";

memoize('slow_func_2');

# define function after memoize

sub slow_func_2 {
  print "\@_ 2 = ".join(" , ", @_)."\n";
}

sub slow_func_2 {
  print "\@_ 3 = ".join(" , ", @_)."\n";
}

print '\&slow_func_2              = '.(\&slow_func_2)."\n";
print '*{slow_func_2}{CODE}       = '.(*{slow_func_2}{CODE})."\n";
print '*{main::slow_func_2}{CODE} = '.(*{main::slow_func_2}{CODE})."\n";

slow_func_1(1,2,3);
slow_func_2(4,5,6);

输出结果为

\&slow_func_1              = CODE(0x1384f0)
*{slow_func_1}{CODE}       = CODE(0x1384f0)
*{main::slow_func_1}{CODE} = CODE(0x1384f0)
memoize slow_func_1 to CODE(0x117c18) -> CODE(0x1384f0)
\&slow_func_1              = CODE(0x117c18)
*{slow_func_1}{CODE}       = CODE(0x117c18)
*{main::slow_func_1}{CODE} = CODE(0x117c18)
memoize slow_func_2 to CODE(0x131800) -> CODE(0x138a60)
\&slow_func_2              = CODE(0x131800)
*{slow_func_2}{CODE}       = CODE(0x131800)
*{main::slow_func_2}{CODE} = CODE(0x131800)
memoize_call CODE(0x1384f0)
@_ 1 = 1 , 2 , 3
memoize_call CODE(0x138a60)
@_ 3 = 4 , 5 , 6

输出结果中的memoize_call表明被调用的是wrapper函数。

在此基础上，实现结果缓存就不再是难事。

Tips

这个模块的名字叫做memoize而不是memorize。