May 31

I’ve been searching for the best way to normalize an argument list to a string, such that two argument lists convert to the same string iff they are equivalent. My ideal algorithm would

  1. Compare embedded hashes and lists deeply, rather than by reference
  2. Ignore hash key order
  3. Ignore difference between 3 and “3″
  4. Generate a relatively readable string
  5. Perform well (XS preferred over Perl)

This is necessary for memoizing a function, or for caching a web page with query arguments.

As a strawman example, Memoize uses this as a default normalizer, which fails #1 and #3:

$argstr = join chr(28),@_;  

The best candidate I’ve found to date is

JSON::XS->new->utf8->canonical

as it is fast, readable, and hash-key-order agnostic. CHI uses this to generate keys from arbitrary references.

However, JSON::XS treats the number 3 and the string “3″ differently, based on how the scalar was used recently. This can generate different strings for essentially equivalent argument lists and reduce the memoization effect. (The vast majority of functions won’t know or care if they get 3 or “3″.)

For fun I looked at a bunch of serializers to see which ones differentiate 3 and “3″:

Data::Dump   : equal - [3] vs [3]
Data::Dumper : not equal - [3] vs ['3']
FreezeThaw   : equal - FrT;@1|@1|$1|3 vs FrT;@1|@1|$1|3
JSON::PP     : not equal - [3] vs ["3"]
JSON::XS     : not equal - [3] vs ["3"]
Storable     : not equal - <unprintable>
YAML         : equal - ---n- 3n vs ---n- 3n
YAML::Syck   : equal - --- n- 3n vs --- n- 3n
YAML::XS     : not equal - ---n- 3n vs ---n- '3'n

It seems in general like the more sophisticated modules make this differentiation, perhaps because it is more “correct”, though it is the opposite of what I want in this case. :) Of the ones that report “equal”, not sure how to get them to ignore hash key order.

I could walk the argument list beforehand and stringify all numbers, but this would require making a deep copy and would violate #5.

If I find a great result that requires more than a few lines of code, I’ll stick it in CPAN, e.g. Params::Normalize.

4 Responses to “Normalizing function arguments for memoization”

  1. Max Says:

    You can try Data::MessagePack with prefer_integer:

    Data::MessagePack->new->canonical->utf8->prefer_integer->pack([ "3" ]) eq Data::MessagePack->new->canonical->utf8->prefer_integer->pack([ 3 ]) and say “OK”

    It is fast and very compact.

    Max.

  2. ilmari Says:

    Data::Pond seems to satisfy all your criteria. It’s basically to Perl what JSON is to Javascript, and is implemented in XS for speed.

    $ perl -MData::Pond=pond_write_datum -E ‘say pond_write_datum([3,"3"])’
    [3,3]

  3. Jonathan Swartz Says:

    Some more discussion at

    http://stackoverflow.com/questions/10835106/how-to-normalize-perl-function-arguments-for-memoization

  4. Jonathan Swartz Says:

    @ilmari Never heard of Data::Pond, thanks, I’ll check it out.

Leave a Reply

preload preload preload