c - 如何在 C 中针对各种大小的缓冲区测试 WKdm 算法

Question

我正在尝试测试 WKdm 算法，看看它对 100KB、1MB 和 10MB 的缓冲区执行得如何；但是，在我下面的测试程序中，任何大于 1KB 的缓冲区都会抛出 EXC_BAD_ACCESS:Could not access memory。

我采用了 WKdm.c 的 main()，这是一个简单的测试，并尝试对其进行转换，以便我可以更改要压缩的输入缓冲区的大小。

我正在使用 WKDM 算法的标准 Scott Kaplan 实现，它由源文件和头文件组成，找到 here .我试过 Linux 和 OS X 32 位。

#include <stdio.h>
#include <unistd.h>
#include <math.h>
#include <strings.h>
#include <sys/time.h>
#include "WKdm.h"

#define PAGE_SIZE_IN_WORDS 1024
#define PAGE_SIZE_IN_BYTES 4096

int main() {

    WK_word i;
    //int testSize = 1024; //1KB Works
    int testSize = 102400; //100KB causes EXC_BAD_ACCESS

    int testNumWords = testSize / sizeof(WK_word);
    printf("testSize = %d bytes or %d words\n", testSize, testNumWords);

    WK_word* source_buf = (WK_word*) malloc(testSize * 2);
    WK_word* dest_buf = (WK_word*) malloc(testSize * 2);
    WK_word* udest_buf = (WK_word*) malloc(testSize * 2);

    for (i = 0; i < testNumWords; i++) {
        source_buf[i] = rand() % 1000; //Semi-random: 0-999 stored in each 4-byte word
    }

    source_buf[testNumWords + 1] = 99999;
    udest_buf[testNumWords + 1] = 55555;

    printf("first 50 words of source_buf are:\n");
    for (i = 0; i < 50; i++)
        printf(" %d", source_buf[i]);
    fflush(stdout);

    struct timeval t0;  struct timeval t1;
    gettimeofday(&t0, 0);

    // Compress the source_buf into the dest_buf
    i = WKdm_compress(source_buf, dest_buf, testNumWords);

    gettimeofday(&t1, 0);
    long elapsed = (t1.tv_sec - t0.tv_sec) * 1000000 + t1.tv_usec - t0.tv_usec;

    printf("\nWKdm_compress size in bytes: %u\n", i);
    printf("Time to compress: %lu microseconds\n\n", elapsed);

    printf("redzone value at end of source buf (should be 99999) is %u\n",
            source_buf[testNumWords + 1]); fflush(stdout);

    gettimeofday(&t0, 0);

    WKdm_decompress(dest_buf, udest_buf, testNumWords);

    gettimeofday(&t1, 0);
    elapsed = (t1.tv_sec - t0.tv_sec) * 1000000 + t1.tv_usec - t0.tv_usec;
    printf("Time to decompress: %lu microseconds\n\n", elapsed);

    printf("redzone value at end of udest buf (should be 55555) is %u\n", udest_buf[testSize + 1]);

    printf("first 50 words of udest_buf are:\n");
    for (i = 0; i < 50; i++)
        printf(" %d", udest_buf[i]);

    i = bcmp(source_buf, udest_buf, 100);

    printf("\nbcmp of orig. and compr'd/decompr'd copy (should be 0) is %u\n", i);
    fflush(stdout);
    return 0;
}

Answer 1

Scott Kaplan 实现的 WKdm 算法专为 4KB 的页面大小而设计。如果要压缩大于 4KB 的任何内容，则需要增加用于在建模期间以中间形式保存输出数据的数组的大小。这 3 个数组位于 WKdm_compress 和 WKdm_decompress 函数的顶部。您可以增加它们的大小以存储更多的中间数据，但看起来压缩/分解时间会显着增加。

此外，压缩大于 1MB 的缓冲区对我来说会导致更多越界异常。因此，除非您想进行大量重写，否则您可能只想对小于 4KB 的缓冲区使用 WKdm。

附带说明一下，Kaplan 的 WKdm 实现针对压缩 4KB 进行了优化，这可能是 Apple 在页面大小为 4KB 的 OS X 10.9 Mavericks 中使用它进行内存压缩的一个重要原因。