setup_osutil_cffi.py

bdiff: don't check border condition in loop

`plast = a + len - 1`. So, this "for" loop iterates from "a" to "plast",
inclusive. So, `p == plast` can only be true on the final iteration
of the loop. So checking for it on every loop iteration is wasteful.

This patch simply decreases the upper bound of the loop by 1 and
adds an explicit check after iteration for the `p == plast` case.
We can't simply add 1 to the initial value for "i" because that
doesn't do the correct thing on empty input strings.

`perfbdiff -m 3041e4d59df2` on the Firefox repo becomes significantly
faster:

! wall 0.072763 comb 0.070000 user 0.070000 sys 0.000000 (best of 100)
! wall 0.053221 comb 0.060000 user 0.060000 sys 0.000000 (best of 100)

For the curious, this code has its origins in 8b067bde6679, which is
the changeset that introduced bdiff.c in 2005.

Also, GNU diffutils is able to perform a similar line-based diff in
under 20ms. So there's likely more perf wins to be found in this code.
One of them is the hashing algorithm. But it looks like mpm spent
some time testing hash collisions in d0c48891dd4a. I'd like to do the
same before switching away from lyhash, just to be on the safe side.

from __future__ import absolute_import

import cffi

ffi = cffi.FFI()
ffi.set_source("_osutil_cffi", """
#include <sys/attr.h>
#include <sys/vnode.h>
#include <unistd.h>
#include <fcntl.h>
#include <time.h>

typedef struct val_attrs {
    uint32_t          length;
    attribute_set_t   returned;
    attrreference_t   name_info;
    fsobj_type_t      obj_type;
    struct timespec   mtime;
    uint32_t          accessmask;
    off_t             datalength;
} __attribute__((aligned(4), packed)) val_attrs_t;
""", include_dirs=['mercurial'])
ffi.cdef('''

typedef uint32_t attrgroup_t;

typedef struct attrlist {
    uint16_t     bitmapcount; /* number of attr. bit sets in list */
    uint16_t   reserved;    /* (to maintain 4-byte alignment) */
    attrgroup_t commonattr;  /* common attribute group */
    attrgroup_t volattr;     /* volume attribute group */
    attrgroup_t dirattr;     /* directory attribute group */
    attrgroup_t fileattr;    /* file attribute group */
    attrgroup_t forkattr;    /* fork attribute group */
    ...;
};

typedef struct attribute_set {
    ...;
} attribute_set_t;

typedef struct attrreference {
    int attr_dataoffset;
    int attr_length;
    ...;
} attrreference_t;

typedef int ... off_t;

typedef struct val_attrs {
    uint32_t          length;
    attribute_set_t   returned;
    attrreference_t   name_info;
    uint32_t          obj_type;
    struct timespec   mtime;
    uint32_t          accessmask;
    off_t             datalength;
    ...;
} val_attrs_t;

/* the exact layout of the above struct will be figured out during build time */

typedef int ... time_t;

typedef struct timespec {
    time_t tv_sec;
    ...;
};

int getattrlist(const char* path, struct attrlist * attrList, void * attrBuf,
                size_t attrBufSize, unsigned int options);

int getattrlistbulk(int dirfd, struct attrlist * attrList, void * attrBuf,
                    size_t attrBufSize, uint64_t options);

#define ATTR_BIT_MAP_COUNT ...
#define ATTR_CMN_NAME ...
#define ATTR_CMN_OBJTYPE ...
#define ATTR_CMN_MODTIME ...
#define ATTR_CMN_ACCESSMASK ...
#define ATTR_CMN_ERROR ...
#define ATTR_CMN_RETURNED_ATTRS ...
#define ATTR_FILE_DATALENGTH ...

#define VREG ...
#define VDIR ...
#define VLNK ...
#define VBLK ...
#define VCHR ...
#define VFIFO ...
#define VSOCK ...

#define S_IFMT ...

int open(const char *path, int oflag, int perm);
int close(int);

#define O_RDONLY ...
''')

if __name__ == '__main__':
    ffi.compile()