perf/micro/hash-table.c

   1 /*
   2  * Copyright © 2011 Andrea Canciani
   3  *
   4  * Permission to use, copy, modify, distribute, and sell this software
   5  * and its documentation for any purpose is hereby granted without
   6  * fee, provided that the above copyright notice appear in all copies
   7  * and that both that copyright notice and this permission notice
   8  * appear in supporting documentation, and that the name of
   9  * Red Hat, Inc. not be used in advertising or publicity pertaining to
  10  * distribution of the software without specific, written prior
  11  * permission. Red Hat, Inc. makes no representations about the
  12  * suitability of this software for any purpose.  It is provided "as
  13  * is" without express or implied warranty.
  14  *
  15  * RED HAT, INC. DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS
  16  * SOFTWARE, INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND
  17  * FITNESS, IN NO EVENT SHALL RED HAT, INC. BE LIABLE FOR ANY SPECIAL,
  18  * INDIRECT OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER
  19  * RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION
  20  * OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR
  21  * IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
  22  *
  23  * Author: Andrea Canciani <ranma42@gmail.com>
  24  */
  25
  26 #include "cairo-perf.h"
  27
  28 #define ITER 1000
  29 #define HOLDOVERS 256
  30 #define LIVE_ENTRIES 257
  31 #define ACTIVE_FONTS (LIVE_ENTRIES - HOLDOVERS - 1)
  32
  33 /*
  34  * The original implementation of hash tables was very inefficient, as
  35  * pointed out in https://bugs.freedesktop.org/show_bug.cgi?id=17399
  36  *
  37  * This benchmark tries to fill up the scaled_font_map hash table to
  38  * show the O(n) behavior.
  39  */
  40
  41 static cairo_time_t
  42 do_hash_table (cairo_t *cr, int width, int height, int loops)
  43 {
  44     /*
  45      * Microsoft C Compiler complains that:
  46      * error C2466: cannot allocate an array of constant size 0
  47      * so we add an unused element to make it happy
  48      */
  49     cairo_scaled_font_t *active_fonts[ACTIVE_FONTS + 1];
  50     cairo_matrix_t m;
  51     int i;
  52
  53     cairo_matrix_init_identity (&m);
  54
  55     /* Touch HOLDOVERS scaled fonts to fill up the holdover list. */
  56     for (i = 0; i < HOLDOVERS; i++) {
  57         m.yy = m.xx * (i + 1);
  58         cairo_set_font_matrix (cr, &m);
  59         cairo_get_scaled_font (cr);
  60     }
  61
  62     /*
  63      * Reference some scaled fonts so that they will be kept in the
  64      * scaled fonts map. We want LIVE_ENTRIES elements in the font
  65      * map, but cairo keeps HOLDOVERS recently used fonts in it and we
  66      * will be activating a new font in the cr context, so we just
  67      * keep references to ACTIVE_FONTS fonts.
  68      *
  69      * Note: setting LIVE_ENTRIES == HOLDOVERS+1 means that we keep no
  70      * font in active_fonts and the slowness is caused by the holdover
  71      * fonts only.
  72      */
  73     for (i = 0; i < ACTIVE_FONTS; i++) {
  74         cairo_scaled_font_t *scaled_font;
  75
  76         m.yy = m.xx * (i + 1);
  77         cairo_set_font_matrix (cr, &m);
  78
  79         scaled_font = cairo_get_scaled_font (cr);
  80         active_fonts[i] = cairo_scaled_font_reference (scaled_font);
  81     }
  82
  83     cairo_perf_timer_start ();
  84     cairo_perf_set_thread_aware (cr, FALSE);
  85
  86     while (loops--) {
  87         if (loops == 0)
  88             cairo_perf_set_thread_aware (cr, TRUE);
  89         m.xx += 1.0;
  90
  91         /* Generate ITER new scaled fonts per loop */
  92         for (i = 0; i < ITER; i++) {
  93             m.yy = m.xx * (i + 1);
  94             cairo_set_font_matrix (cr, &m);
  95             cairo_get_scaled_font (cr);
  96         }
  97     }
  98
  99     cairo_perf_timer_stop ();
 100
 101     for (i = 0; i < ACTIVE_FONTS; i++)
 102         cairo_scaled_font_destroy (active_fonts[i]);
 103
 104     return cairo_perf_timer_elapsed ();
 105 }
 106
 107 cairo_bool_t
 108 hash_table_enabled (cairo_perf_t *perf)
 109 {
 110     return cairo_perf_can_run (perf, "hash-table", NULL);
 111 }
 112
 113 void
 114 hash_table (cairo_perf_t *perf, cairo_t *cr, int width, int height)
 115 {
 116     cairo_perf_cover_sources_and_operators (perf, "hash-table",
 117                                             do_hash_table, NULL);
 118 }