tests/collections_perf.c

   1 /*
   2 * Copyright (c) 2020 Apple Inc. All rights reserved.
   3 *
   4 * @APPLE_LICENSE_HEADER_START@
   5 *
   6 * This file contains Original Code and/or Modifications of Original Code
   7 * as defined in and that are subject to the Apple Public Source License
   8 * Version 2.0 (the 'License'). You may not use this file except in
   9 * compliance with the License. Please obtain a copy of the License at
  10 * http://www.opensource.apple.com/apsl/ and read it before using this
  11 * file.
  12 *
  13 * The Original Code and all software distributed under the License are
  14 * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
  15 * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
  16 * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
  17 * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
  18 * Please see the License for the specific language governing rights and
  19 * limitations under the License.
  20 *
  21 * @APPLE_LICENSE_HEADER_END@
  22 */
  23
  24 #import <TargetConditionals.h>
  25 #include <os/collections.h>
  26 #include <stdio.h>
  27 #include <string.h>
  28 #include <unistd.h>
  29 #include <darwintest.h>
  30 #include <stdlib.h>
  31 #include <sys/resource.h>
  32 #include <libproc.h>
  33 #include <sys/fcntl.h>
  34
  35
  36 // 11400714819323198485 is coprime with 2^64, so this will touch every number
  37 // before looping. It's also the closest number to 2^64 / the golden ratio, so
  38 // it will give a pretty even distribution
  39 static inline uint64_t _seq_next(uint64_t prev) {
  40         return prev + 11400714819323198485llu;
  41 }
  42
  43 #define MAPS_COUNT 4096
  44 #define ACTIONS_PER_MEASUREMENT_COUNT 512
  45 #define INSERT_TO_FIND_RATIO 64
  46 #define TOTAL_ITERATIONS 16
  47
  48 #define PERF_OUTPUT_FILENAME "/tmp/libcollection_perf_data.csv"
  49
  50 // This is fairly arbitrary, and just makes sure that any value bias is fairly
  51 // accounted for
  52 static inline uint64_t _value_for_key(uint64_t key) {
  53         return key ^ 0xFFFF0000FF0000FF;
  54 }
  55
  56 static uint64_t _insert_n_entries_to_maps(os_map_64_t *maps, uint64_t seed) {
  57         uint64_t current_seq = seed;
  58         for ( int i = 0; i < ACTIONS_PER_MEASUREMENT_COUNT; i++){
  59                 void *value = (void *)_value_for_key(current_seq);
  60                 for (int j = 0; j < MAPS_COUNT; j++) {
  61                         os_map_insert(&maps[j], current_seq, value);
  62                 }
  63                 current_seq = _seq_next(current_seq);
  64         }
  65         return current_seq;
  66 }
  67
  68 static uint64_t _find_n_entries_in_maps(os_map_64_t *maps, uint64_t seed) {
  69         uint64_t current_seq = seed;
  70         for ( int i = 0; i < ACTIONS_PER_MEASUREMENT_COUNT; i++){
  71                 for (int j = 0; j < MAPS_COUNT; j++) {
  72                         (void)os_map_find(&maps[j], current_seq);
  73                 }
  74                 current_seq = _seq_next(current_seq);
  75         }
  76         return current_seq;
  77 }
  78
  79 uint64_t absoluteTimeFromMachTime(uint64_t machTime) {
  80     // get the mach timescale
  81     static double __TimeScale = 0.0;
  82     if (__TimeScale == 0.0) {
  83         struct mach_timebase_info info;
  84         if (mach_timebase_info(&info) == KERN_SUCCESS) {
  85             __TimeScale = ((double)info.numer / (double)info.denom);
  86         }
  87     }
  88     return (uint64_t)(machTime * __TimeScale);
  89 }
  90
  91 static uint64_t
  92 _get_dirtymemory()
  93 {
  94     int rval = 0;
  95     struct rusage_info_v4 rusage;
  96     if (proc_pid_rusage(getpid(), RUSAGE_INFO_V4, (rusage_info_t)&rusage)) {
  97             rval = errno;
  98             T_FAIL("rusage failed with %d", rval);
  99             return 0;
 100     } else {
 101             return rusage.ri_phys_footprint;
 102     }
 103 }
 104
 105 T_DECL(map_perf, "Test map performance for small hash maps",
 106                 T_META("owner", "Core Darwin Daemons & Tools"),
 107                 T_META_CHECK_LEAKS(false),
 108                 T_META_ASROOT(true))
 109 {
 110 #if !(TARGET_OS_IOS | TARGET_OS_OSX)
 111         T_PASS("Map_perf doesn't run on this platform");
 112         return;
 113 #endif
 114
 115         os_map_64_t perf_maps[MAPS_COUNT];
 116
 117         for (int i = 0; i < MAPS_COUNT; i++) {
 118                 os_map_init(&perf_maps[i], NULL);
 119         }
 120
 121         uint64_t current_seq = _seq_next(0);
 122
 123
 124         int output_fd = creat(PERF_OUTPUT_FILENAME, S_IWUSR);
 125         assert(output_fd);
 126         FILE *output_file = fdopen(output_fd, "w");
 127         assert(output_file);
 128
 129         fprintf(output_file,
 130                 "MAP_SIZE,INSERT_TIME,FIND_TIME,FIND_MISSING_TIME,MEM_USAGE\n");
 131
 132         uint64_t baseline_memory_usage = _get_dirtymemory();
 133         T_LOG("Baseline memory usage is %llu", baseline_memory_usage);
 134
 135         for (int i = 0; i < TOTAL_ITERATIONS; i++) {
 136                 uint64_t map_size = ACTIONS_PER_MEASUREMENT_COUNT * (i + 1);
 137                 T_LOG("Starting performance testing with map size %llu",
 138                       map_size);
 139
 140                 uint64_t insert_start_mach_time = mach_absolute_time();
 141                 uint64_t next_seq = _insert_n_entries_to_maps(perf_maps,
 142                                                               current_seq);
 143                 uint64_t insert_end_mach_time = mach_absolute_time();
 144
 145                 uint64_t insert_start_time = absoluteTimeFromMachTime(insert_start_mach_time);
 146                 uint64_t insert_end_time = absoluteTimeFromMachTime(insert_end_mach_time);
 147
 148                 T_LOG("Insertions complete, with start time %llu, end time %llu",
 149                       insert_start_time, insert_end_time);
 150
 151                 uint64_t insert_average_time = ((insert_end_time - insert_start_time)) /
 152                         (MAPS_COUNT * ACTIONS_PER_MEASUREMENT_COUNT);
 153
 154                 T_LOG("DATA: INSERTION TIME %llu, %llu", map_size,
 155                       insert_average_time);
 156
 157                 uint64_t find_start_mach_time = mach_absolute_time();
 158                 for (int j = 0; j < INSERT_TO_FIND_RATIO; j++) {
 159                         _find_n_entries_in_maps(perf_maps, current_seq);
 160                 }
 161                 uint64_t find_end_mach_time = mach_absolute_time();
 162
 163                 uint64_t find_start_time = absoluteTimeFromMachTime(find_start_mach_time);
 164                 uint64_t find_end_time = absoluteTimeFromMachTime(find_end_mach_time);
 165
 166                 T_LOG("Finds complete, with start time %llu, end time %llu",
 167                       find_start_time, find_end_time);
 168
 169                 uint64_t find_average_time = ((find_end_time - find_start_time)) /
 170                         (MAPS_COUNT * ACTIONS_PER_MEASUREMENT_COUNT * INSERT_TO_FIND_RATIO);
 171
 172                 T_LOG("DATA: FIND TIME FOR %llu, %llu", map_size,
 173                       find_average_time);
 174
 175                 uint64_t no_find_start_mach_time = mach_absolute_time();
 176                 for (int j = 0; j < INSERT_TO_FIND_RATIO; j++) {
 177                         _find_n_entries_in_maps(perf_maps, next_seq);
 178                 }
 179                 uint64_t no_find_end_mach_time = mach_absolute_time();
 180
 181                 uint64_t no_find_start_time = absoluteTimeFromMachTime(no_find_start_mach_time);
 182                 uint64_t no_find_end_time = absoluteTimeFromMachTime(no_find_end_mach_time);
 183
 184                 T_LOG("Find not present complete, with start time %llu, end time %llu",
 185                       no_find_start_time, no_find_end_time);
 186
 187                 uint64_t no_find_average_time = ((no_find_end_time - no_find_start_time)) /
 188                         (MAPS_COUNT * ACTIONS_PER_MEASUREMENT_COUNT * INSERT_TO_FIND_RATIO);
 189
 190                 T_LOG("DATA: NO-FIND TIME FOR %llu, %llu",
 191                       map_size, no_find_average_time);
 192
 193
 194                 uint64_t latest_memory_usage = _get_dirtymemory();
 195                 T_LOG("New memory usage is %llu", latest_memory_usage);
 196
 197                 uint64_t average_memory_usage = latest_memory_usage / MAPS_COUNT;
 198                 T_LOG("DATA: MEMORY USAGE FOR %llu, %llu", map_size,
 199                       average_memory_usage);
 200
 201                 fprintf(output_file, "%llu,%llu,%llu,%llu,%llu\n", map_size,
 202                         insert_average_time, find_average_time,
 203                         no_find_average_time, average_memory_usage);
 204
 205                 current_seq = next_seq;
 206         }
 207
 208         fclose(output_file);
 209         close(output_fd);
 210
 211         T_PASS("Finished, output generated at: " PERF_OUTPUT_FILENAME);
 212 }