[apple/libc.git] / tests / collections_perf.c

/*
* Copyright (c) 2020 Apple Inc. All rights reserved.
*
* @APPLE_LICENSE_HEADER_START@
*
* This file contains Original Code and/or Modifications of Original Code
* as defined in and that are subject to the Apple Public Source License
* Version 2.0 (the 'License'). You may not use this file except in
* compliance with the License. Please obtain a copy of the License at
* http://www.opensource.apple.com/apsl/ and read it before using this
* file.
*
* The Original Code and all software distributed under the License are
* distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
* EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
* INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
* FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
* Please see the License for the specific language governing rights and
* limitations under the License.
*
* @APPLE_LICENSE_HEADER_END@
*/

#import <TargetConditionals.h>
#include <os/collections.h>
#include <stdio.h>
#include <string.h>
#include <unistd.h>
#include <darwintest.h>
#include <stdlib.h>
#include <sys/resource.h>
#include <libproc.h>
#include <sys/fcntl.h>


// 11400714819323198485 is coprime with 2^64, so this will touch every number
// before looping. It's also the closest number to 2^64 / the golden ratio, so
// it will give a pretty even distribution
static inline uint64_t _seq_next(uint64_t prev) {
	return prev + 11400714819323198485llu;
}

#define MAPS_COUNT 4096
#define ACTIONS_PER_MEASUREMENT_COUNT 512
#define INSERT_TO_FIND_RATIO 64
#define TOTAL_ITERATIONS 16

#define PERF_OUTPUT_FILENAME "/tmp/libcollection_perf_data.csv"

// This is fairly arbitrary, and just makes sure that any value bias is fairly
// accounted for
static inline uint64_t _value_for_key(uint64_t key) {
	return key ^ 0xFFFF0000FF0000FF;
}

static uint64_t _insert_n_entries_to_maps(os_map_64_t *maps, uint64_t seed) {
	uint64_t current_seq = seed;
	for ( int i = 0; i < ACTIONS_PER_MEASUREMENT_COUNT; i++){
		void *value = (void *)_value_for_key(current_seq);
		for (int j = 0; j < MAPS_COUNT; j++) {
			os_map_insert(&maps[j], current_seq, value);
		}
		current_seq = _seq_next(current_seq);
	}
	return current_seq;
}

static uint64_t _find_n_entries_in_maps(os_map_64_t *maps, uint64_t seed) {
	uint64_t current_seq = seed;
	for ( int i = 0; i < ACTIONS_PER_MEASUREMENT_COUNT; i++){
		for (int j = 0; j < MAPS_COUNT; j++) {
			(void)os_map_find(&maps[j], current_seq);
		}
		current_seq = _seq_next(current_seq);
	}
	return current_seq;
}

uint64_t absoluteTimeFromMachTime(uint64_t machTime) {
    // get the mach timescale
    static double __TimeScale = 0.0;
    if (__TimeScale == 0.0) {
        struct mach_timebase_info info;
        if (mach_timebase_info(&info) == KERN_SUCCESS) {
            __TimeScale = ((double)info.numer / (double)info.denom);
        }
    }
    return (uint64_t)(machTime * __TimeScale);
}

static uint64_t
_get_dirtymemory()
{
    int rval = 0;
    struct rusage_info_v4 rusage;
    if (proc_pid_rusage(getpid(), RUSAGE_INFO_V4, (rusage_info_t)&rusage)) {
	    rval = errno;
	    T_FAIL("rusage failed with %d", rval);
	    return 0;
    } else {
	    return rusage.ri_phys_footprint;
    }
}

T_DECL(map_perf, "Test map performance for small hash maps",
		T_META("owner", "Core Darwin Daemons & Tools"),
		T_META_CHECK_LEAKS(false),
		T_META_ASROOT(true))
{
#if !(TARGET_OS_IOS | TARGET_OS_OSX)
	T_PASS("Map_perf doesn't run on this platform");
	return;
#endif

	os_map_64_t perf_maps[MAPS_COUNT];

	for (int i = 0; i < MAPS_COUNT; i++) {
		os_map_init(&perf_maps[i], NULL);
	}

	uint64_t current_seq = _seq_next(0);


	int output_fd = creat(PERF_OUTPUT_FILENAME, S_IWUSR);
	assert(output_fd);
	FILE *output_file = fdopen(output_fd, "w");
	assert(output_file);

	fprintf(output_file,
		"MAP_SIZE,INSERT_TIME,FIND_TIME,FIND_MISSING_TIME,MEM_USAGE\n");

	uint64_t baseline_memory_usage = _get_dirtymemory();
	T_LOG("Baseline memory usage is %llu", baseline_memory_usage);

	for (int i = 0; i < TOTAL_ITERATIONS; i++) {
		uint64_t map_size = ACTIONS_PER_MEASUREMENT_COUNT * (i + 1);
		T_LOG("Starting performance testing with map size %llu",
		      map_size);

		uint64_t insert_start_mach_time = mach_absolute_time();
		uint64_t next_seq = _insert_n_entries_to_maps(perf_maps,
							      current_seq);
		uint64_t insert_end_mach_time = mach_absolute_time();

		uint64_t insert_start_time = absoluteTimeFromMachTime(insert_start_mach_time);
		uint64_t insert_end_time = absoluteTimeFromMachTime(insert_end_mach_time);

		T_LOG("Insertions complete, with start time %llu, end time %llu",
		      insert_start_time, insert_end_time);

		uint64_t insert_average_time = ((insert_end_time - insert_start_time)) /
			(MAPS_COUNT * ACTIONS_PER_MEASUREMENT_COUNT);

		T_LOG("DATA: INSERTION TIME %llu, %llu", map_size,
		      insert_average_time);

		uint64_t find_start_mach_time = mach_absolute_time();
		for (int j = 0; j < INSERT_TO_FIND_RATIO; j++) {
			_find_n_entries_in_maps(perf_maps, current_seq);
		}
		uint64_t find_end_mach_time = mach_absolute_time();

		uint64_t find_start_time = absoluteTimeFromMachTime(find_start_mach_time);
		uint64_t find_end_time = absoluteTimeFromMachTime(find_end_mach_time);

		T_LOG("Finds complete, with start time %llu, end time %llu",
		      find_start_time, find_end_time);

		uint64_t find_average_time = ((find_end_time - find_start_time)) /
			(MAPS_COUNT * ACTIONS_PER_MEASUREMENT_COUNT * INSERT_TO_FIND_RATIO);

		T_LOG("DATA: FIND TIME FOR %llu, %llu", map_size,
		      find_average_time);

		uint64_t no_find_start_mach_time = mach_absolute_time();
		for (int j = 0; j < INSERT_TO_FIND_RATIO; j++) {
			_find_n_entries_in_maps(perf_maps, next_seq);
		}
		uint64_t no_find_end_mach_time = mach_absolute_time();

		uint64_t no_find_start_time = absoluteTimeFromMachTime(no_find_start_mach_time);
		uint64_t no_find_end_time = absoluteTimeFromMachTime(no_find_end_mach_time);

		T_LOG("Find not present complete, with start time %llu, end time %llu",
		      no_find_start_time, no_find_end_time);

		uint64_t no_find_average_time = ((no_find_end_time - no_find_start_time)) /
			(MAPS_COUNT * ACTIONS_PER_MEASUREMENT_COUNT * INSERT_TO_FIND_RATIO);

		T_LOG("DATA: NO-FIND TIME FOR %llu, %llu",
		      map_size, no_find_average_time);


		uint64_t latest_memory_usage = _get_dirtymemory();
		T_LOG("New memory usage is %llu", latest_memory_usage);

		uint64_t average_memory_usage = latest_memory_usage / MAPS_COUNT;
		T_LOG("DATA: MEMORY USAGE FOR %llu, %llu", map_size,
		      average_memory_usage);

		fprintf(output_file, "%llu,%llu,%llu,%llu,%llu\n", map_size,
			insert_average_time, find_average_time,
			no_find_average_time, average_memory_usage);

		current_seq = next_seq;
	}

	fclose(output_file);
	close(output_fd);

	T_PASS("Finished, output generated at: " PERF_OUTPUT_FILENAME);
}
Commit	Line	Data
a9aaacca A	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	}