crccache/benchmark.c

   1 #include <sys/types.h>
   2 #include <sys/stat.h>
   3 #include <fcntl.h>
   4 #include <stdio.h>
   5 #include <stdlib.h>
   6 #include <string.h>
   7 #include <unistd.h>
   8 #include <errno.h>
   9 #include <time.h>
  10 #include <apr_sha1.h>
  11 #include "zlib.h"
  12 #include <crcsync/crcsync.h>
  13
  14 #define FULL_BLOCK_COUNT 40
  15 const int HASH_SIZE = 64;
  16 const int TEST_ITERATIONS_COUNT = 100;
  17
  18 void error(char *msg)
  19 {
  20         printf("Error code: %d, msg: %s", errno, msg);
  21         exit(1);
  22 }
  23
  24 typedef struct
  25 {
  26         unsigned char *buf;
  27         size_t bufsize;
  28         size_t datasize;
  29 } data_t;
  30
  31 data_t *init_data()
  32 {
  33         data_t *data = malloc(sizeof(data));
  34         if (data == NULL)
  35         {
  36                 error("Can not allocate data_t structure");
  37         }
  38         data->bufsize = 10000;
  39         data->datasize = 0;
  40         data->buf = malloc(data->bufsize);
  41         if (data->buf == NULL)
  42         {
  43                 error("Can not allocate databuf");
  44         }
  45         return data;
  46 }
  47
  48 void append_data(data_t *data, unsigned char *buf, ssize_t bufsize)
  49 {
  50         while (data->datasize + bufsize > data->bufsize)
  51         {
  52                 unsigned char *newdatabuf = realloc(data->buf, data->bufsize*2);
  53                 if (newdatabuf == NULL)
  54                 {
  55                         error("Can not re-allocate databuf");
  56                 }
  57                 data->buf = newdatabuf;
  58                 data->bufsize *= 2;
  59         }
  60         memcpy(data->buf + data->datasize, buf, bufsize);
  61         data->datasize += bufsize;
  62 }
  63
  64 void free_data(data_t *data)
  65 {
  66         free(data->buf);
  67         free(data);
  68 }
  69
  70 data_t *read_file_to_data(char *fname)
  71 {
  72         int fh = open(fname, O_RDONLY);
  73         if (fh == -1)
  74         {
  75                 error("Can not open file");
  76         }
  77
  78         data_t *data = init_data();
  79         unsigned char readbuf[1000];
  80         ssize_t nread;
  81         while ((nread = read(fh, readbuf, sizeof(readbuf))) != 0)
  82         {
  83                 append_data(data, readbuf, nread);
  84         }
  85
  86         close(fh);
  87
  88         return data;
  89 }
  90
  91
  92 void crcvalidate_data(data_t *data, struct crc_context *crcctx)
  93 {
  94
  95         long rd_block_rslt;
  96         unsigned char *getpos = data->buf;
  97         ssize_t remaining = data->datasize;
  98         // printf("rslts: ");
  99         while (remaining != 0)
 100         {
 101                 size_t ndigested = crc_read_block(crcctx, &rd_block_rslt, getpos, remaining);
 102                 // printf("%ld ", rd_block_rslt);
 103                 getpos += ndigested;
 104                 remaining -= ndigested;
 105         }
 106         rd_block_rslt = crc_read_flush(crcctx);
 107         // printf("%ld ", rd_block_rslt);
 108         // printf("\n");
 109         crc_reset_running_crcs(crcctx);
 110 }
 111
 112 void sha1_data(data_t *data)
 113 {
 114         /* output SHA1 hash - this will be binary data */
 115         unsigned char hash[ APR_SHA1_DIGESTSIZE ];
 116         apr_sha1_ctx_t sha1_ctx;
 117
 118         apr_sha1_init(&sha1_ctx);
 119         apr_sha1_update_binary(&sha1_ctx, data->buf, data->datasize);
 120         apr_sha1_final(hash, &sha1_ctx);
 121 }
 122
 123 ssize_t compress_tst(unsigned char *org_data_buf, size_t orglen, unsigned char *compressed_data_buf, size_t compressed_size)
 124 {
 125         z_stream compression_stream;
 126         compression_stream.zalloc = Z_NULL;
 127         compression_stream.zfree = Z_NULL;
 128         compression_stream.opaque = Z_NULL;
 129         int zRC = deflateInit(&compression_stream, Z_DEFAULT_COMPRESSION);
 130         if (zRC != Z_OK)
 131         {
 132                 error("deflateInit returned an error code");
 133         }
 134         compression_stream.avail_in = orglen;
 135         compression_stream.next_in = org_data_buf;
 136         compression_stream.avail_out = compressed_size;
 137         compression_stream.next_out = compressed_data_buf;
 138         zRC = deflate(&compression_stream, Z_FINISH);
 139         if (zRC == Z_STREAM_ERROR)
 140         {
 141                 error("deflate returned Z_ERROR");
 142         }
 143         if (compression_stream.avail_in != 0)
 144         {
 145                 error("decompression buffer was too small");
 146         }
 147         return compressed_size - compression_stream.avail_out;
 148 }
 149
 150 ssize_t decompress_tst(unsigned char *org_data_buf, size_t org_size, unsigned char *compressed_data_buf, size_t compressed_len)
 151 {
 152         z_stream decompression_stream;
 153         decompression_stream.zalloc = Z_NULL;
 154         decompression_stream.zfree = Z_NULL;
 155         decompression_stream.opaque = Z_NULL;
 156         decompression_stream.avail_in = 0;
 157         decompression_stream.next_in = Z_NULL;
 158         int zRC = inflateInit(&decompression_stream);
 159         if (zRC != Z_OK)
 160         {
 161                 error("inflateInit returned an error code");
 162         }
 163         decompression_stream.avail_in = compressed_len;
 164         decompression_stream.next_in = compressed_data_buf;
 165         decompression_stream.avail_out = org_size;
 166         decompression_stream.next_out = org_data_buf;
 167         zRC = inflate(&decompression_stream, Z_NO_FLUSH);
 168         if (zRC == Z_NEED_DICT || zRC == Z_DATA_ERROR || zRC == Z_MEM_ERROR)
 169         {
 170                 error("inflate returned Z_NEED_DIC, Z_DATA_ERROR or Z_MEM_ERROR");
 171         }
 172         if (decompression_stream.avail_in != 0)
 173         {
 174                 error("org data buffer was too small");
 175         }
 176         if (zRC != Z_STREAM_END)
 177         {
 178                 error("inflate did not return Z_STREAM_END");
 179         }
 180         return org_size - decompression_stream.avail_out;
 181 }
 182
 183
 184 int contains(uint64_t *hashes, uint64_t value, int cnt)
 185 {
 186         while (cnt-- != 0)
 187         {
 188                 if (hashes[cnt] == value)
 189                 {
 190                         return 1;
 191                 }
 192         }
 193         return 0;
 194 }
 195
 196 typedef struct
 197 {
 198         clock_t start;
 199         clock_t end;
 200 } benchmark_t;
 201
 202 double duration_ms(benchmark_t *bm)
 203 {
 204         return 1000 * (bm->end - bm->start + 0.0)/CLOCKS_PER_SEC;
 205 }
 206
 207 int main(int argc, char *argv[])
 208 {
 209         int cnt;
 210
 211         int merge_trailing_blocks_in_last_block;
 212         for (merge_trailing_blocks_in_last_block = 0; merge_trailing_blocks_in_last_block != 2; merge_trailing_blocks_in_last_block++)
 213         {
 214         // Load the data
 215         data_t *original_data = read_file_to_data(argv[1]);
 216         printf("Original data size: %zu\n", original_data->datasize);
 217
 218         //Set-up buffer for compressed data. Make it twice as long as the original_data
 219         // so that even in a worst-case scenario of totally non-compressable data, it will still
 220         // fit, withouth causing an buffer overflow
 221         data_t *compressed_data = init_data();
 222         append_data(compressed_data, original_data->buf, original_data->bufsize);
 223         append_data(compressed_data, original_data->buf, original_data->bufsize);
 224         // Benchmark the compression
 225         benchmark_t bm_compress;
 226         bm_compress.start = clock();
 227         for (cnt=0; cnt != TEST_ITERATIONS_COUNT; cnt++)
 228         {
 229                 compressed_data->datasize = compress_tst(original_data->buf, original_data->datasize, compressed_data->buf, compressed_data->bufsize);
 230         }
 231         bm_compress.end = clock();
 232         printf("Compressed data size: %zu\n", compressed_data->datasize);
 233
 234
 235         // Parameters for the hashes
 236         size_t block_size = original_data->datasize/FULL_BLOCK_COUNT;
 237         size_t tail_block_size = original_data->datasize%FULL_BLOCK_COUNT;
 238         if (merge_trailing_blocks_in_last_block)
 239         {
 240                 tail_block_size += block_size;
 241         }
 242         size_t block_count_including_final_block = FULL_BLOCK_COUNT + (tail_block_size != 0 && !merge_trailing_blocks_in_last_block);
 243
 244         // Set-up hashes for a perfect match and benchmark how long it takes
 245         uint64_t match_hashes[block_count_including_final_block];
 246         benchmark_t bm_crccalculate;
 247         bm_crccalculate.start = clock();
 248         for (cnt=0; cnt != TEST_ITERATIONS_COUNT; cnt++)
 249         {
 250                 crc_of_blocks(original_data->buf, original_data->datasize, block_size, tail_block_size, HASH_SIZE, match_hashes);
 251         }
 252         bm_crccalculate.end = clock();
 253
 254         // Benchmark reconstructing a page from literal blocks
 255         unsigned char *reconstructed_buf = malloc(original_data->datasize);
 256         benchmark_t bm_reconstruct;
 257         bm_reconstruct.start = clock();
 258         for (cnt=0; cnt != TEST_ITERATIONS_COUNT; cnt++)
 259         {
 260                 int blocks_cnt;
 261                 for (blocks_cnt=0; blocks_cnt != FULL_BLOCK_COUNT; blocks_cnt++)
 262                 {
 263                         memcpy(reconstructed_buf+blocks_cnt*block_size, (original_data->buf)+blocks_cnt*block_size, block_size);
 264                 }
 265                 if (tail_block_size != 0 && !merge_trailing_blocks_in_last_block)
 266                 {
 267                         memcpy(reconstructed_buf+blocks_cnt*block_size, (original_data->buf)+blocks_cnt*block_size, tail_block_size);
 268                 }
 269         }
 270         bm_reconstruct.end = clock();
 271
 272         // Set-up hashes for a perfect mismatch
 273         uint64_t nomatch_hashes[block_count_including_final_block];
 274         uint64_t value = 0;
 275         for (cnt=0; cnt != block_count_including_final_block; cnt++)
 276         {
 277                 while (contains(match_hashes, value, block_count_including_final_block))
 278                 {
 279                         value++;
 280                 }
 281                 nomatch_hashes[cnt] = value;
 282         }
 283
 284         struct crc_context *crcctx;
 285         benchmark_t bm_crc_context_new;
 286         bm_crc_context_new.start = clock();
 287         for (cnt=0; cnt != TEST_ITERATIONS_COUNT; cnt++)
 288         {
 289                 crcctx = crc_context_new(block_size, HASH_SIZE, match_hashes, block_count_including_final_block, tail_block_size);
 290         }
 291         bm_crc_context_new.end = clock();
 292
 293         benchmark_t bm_crcvalidate_match;
 294         bm_crcvalidate_match.start = clock();
 295         for (cnt=0; cnt != TEST_ITERATIONS_COUNT; cnt++)
 296         {
 297                 crcvalidate_data(original_data, crcctx);
 298         }
 299         bm_crcvalidate_match.end = clock();
 300
 301         crcctx = crc_context_new(block_size, HASH_SIZE, nomatch_hashes, block_count_including_final_block, tail_block_size);
 302         benchmark_t bm_crcvalidate_nomatch;
 303         bm_crcvalidate_nomatch.start = clock();
 304         for (cnt=0; cnt != TEST_ITERATIONS_COUNT; cnt++)
 305         {
 306                 crcvalidate_data(original_data, crcctx);
 307         }
 308         bm_crcvalidate_nomatch.end = clock();
 309
 310         crc_context_free(crcctx);
 311
 312         benchmark_t bm_sha1;
 313         bm_sha1.start = clock();
 314         for (cnt=0; cnt != TEST_ITERATIONS_COUNT; cnt++)
 315         {
 316                 sha1_data(original_data);
 317         }
 318         bm_sha1.end = clock();
 319
 320         benchmark_t bm_decompress;
 321         bm_decompress.start = clock();
 322         for (cnt=0; cnt != TEST_ITERATIONS_COUNT; cnt++)
 323         {
 324                 original_data->datasize = decompress_tst(original_data->buf, original_data->bufsize, compressed_data->buf, compressed_data->datasize);
 325         }
 326         bm_decompress.end = clock();
 327         printf("Original data size after decompression: %zd\n", original_data->datasize);
 328
 329         printf(
 330                         "Nblocks: %zd, Block size: %zd, Tail block size: %zd, Compress: %.4f ms, Decompress: %.4f ms, Copy blocks: %.4f ms, New CRCCTX: %.4f ms, Calculate CRCs: %.4f ms, Validate match: %.4f ms, Validate nomatch: %.4f ms, SHA1: %.4f ms\n",
 331                         block_count_including_final_block, block_size, tail_block_size,
 332                         duration_ms(&bm_compress)/TEST_ITERATIONS_COUNT,
 333                         duration_ms(&bm_decompress)/TEST_ITERATIONS_COUNT,
 334                         duration_ms(&bm_reconstruct)/TEST_ITERATIONS_COUNT,
 335                         duration_ms(&bm_crc_context_new)/TEST_ITERATIONS_COUNT,
 336                         duration_ms(&bm_crccalculate)/TEST_ITERATIONS_COUNT,
 337                         duration_ms(&bm_crcvalidate_match)/TEST_ITERATIONS_COUNT,
 338                         duration_ms(&bm_crcvalidate_nomatch)/TEST_ITERATIONS_COUNT,
 339                         duration_ms(&bm_sha1)/TEST_ITERATIONS_COUNT
 340                         );
 341 //      printf(
 342 //                      "Nblocks: %zd, Block size: %zd, Tail block size: %zd, New CRCCTX: %.4f ms, Calculate CRCs: %.4f ms, Validate match: %.4f ms, Validate nomatch: %.4f ms\n",
 343 //                      block_count_including_final_block, block_size, tail_block_size,
 344 //                      duration_ms(&bm_crc_context_new)/TEST_ITERATIONS_COUNT,
 345 //                      duration_ms(&bm_crccalculate)/TEST_ITERATIONS_COUNT,
 346 //                      duration_ms(&bm_crcvalidate_match)/TEST_ITERATIONS_COUNT,
 347 //                      duration_ms(&bm_crcvalidate_nomatch)/TEST_ITERATIONS_COUNT
 348 //                      );
 349
 350         free_data(original_data);
 351         }
 352         return 0;
 353 }