This actually has nothing to do with a.out vs. ELF.  It has to do with
the `new' malloc(3).  I tested 3 versions of file(1):

1) the current version in CVS, with a recent libc, compiled on ELF:

        0.59 real         0.32 user         0.14 sys

2) same, but modified so that maxmagic is strictly a power of 2
   (slightly different than your patch):

        0.15 real         0.05 user         0.04 sys

3) the unedited version, but with the old BSD malloc(3):

        0.15 real         0.06 user         0.05 sys

Draw your own conclusions.