Tarantool development patches archive
 help / color / mirror / Atom feed
* [Tarantool-patches] [PATCH v2 0/3] change small allocator behavior
@ 2020-12-23 13:14 mechanik20051988
  2020-12-23 13:14 ` [Tarantool-patches] [PATCH] memtx: " mechanik20051988
                   ` (3 more replies)
  0 siblings, 4 replies; 14+ messages in thread
From: mechanik20051988 @ 2020-12-23 13:14 UTC (permalink / raw)
  To: v.shpilevoy; +Cc: tarantool-patches

Branch: https://github.com/tarantool/small/tree/mechanik20051988/gh-5216-fix-strange-allocator-behavior
Pull request: https://github.com/tarantool/small/pull/27

Thank you for the previous review. All answers on you questions 
are in the corresponding patches.

Aleksandr Lyapunov (1):
  small: implement new size class evaluation

mechanik20051988 (2):
  test: add small allocator performance test
  small: changed small allocator pool management

 CMakeLists.txt                     |   5 +
 LICENSE                            |   2 +-
 perf/.gitignore                    |   1 +
 perf/CMakeLists.txt                |   7 +
 perf/small_alloc_perf.c            | 375 +++++++++++++++++++++++++++++
 small/small.c                      | 216 ++++-------------
 small/small.h                      |  47 ++--
 small/small_class.c                |  56 +++++
 small/small_class.h                | 218 +++++++++++++++++
 test/CMakeLists.txt                |   9 +
 test/small_class.c                 | 176 ++++++++++++++
 test/small_class.result            |  15 ++
 test/small_class_branchless.result |  15 ++
 13 files changed, 944 insertions(+), 198 deletions(-)
 create mode 100644 perf/.gitignore
 create mode 100644 perf/CMakeLists.txt
 create mode 100644 perf/small_alloc_perf.c
 create mode 100644 small/small_class.c
 create mode 100644 small/small_class.h
 create mode 100644 test/small_class.c
 create mode 100644 test/small_class.result
 create mode 100644 test/small_class_branchless.result

-- 
2.20.1

^ permalink raw reply	[flat|nested] 14+ messages in thread

* [Tarantool-patches] [PATCH] memtx: change small allocator behavior
  2020-12-23 13:14 [Tarantool-patches] [PATCH v2 0/3] change small allocator behavior mechanik20051988
@ 2020-12-23 13:14 ` mechanik20051988
  2020-12-24 15:13   ` Vladislav Shpilevoy
  2020-12-23 13:14 ` [Tarantool-patches] [PATCH v2 1/3] small: implement new size class evaluation mechanik20051988
                   ` (2 subsequent siblings)
  3 siblings, 1 reply; 14+ messages in thread
From: mechanik20051988 @ 2020-12-23 13:14 UTC (permalink / raw)
  To: v.shpilevoy; +Cc: mechanik20051988, tarantool-patches

From: mechanik20051988 <mechanik20.05.1988@gmail.com>

Branch: https://github.com/tarantool/tarantool/tree/mechanik20051988/gh-5216-fix-strange-allocator-behavior
Pull request: https://github.com/tarantool/tarantool/pull/5503

Thank you for the previous review. Here some answers on you questions.
1. I add subsystem name prefix for the commit title
2. As you can see at this moment, small_alloc_create already 
   has restrictions on alloc_factor (see small.c in master branch)
   They change it silently. 
   if (alloc_factor > 2.0)
		alloc_factor = 2.0;
   /*
    * Correct the user-supplied alloc_factor to ensure that
    * it actually produces growing object sizes.
    */
   if (alloc->step_pool_objsize_max * alloc_factor <
	   alloc->step_pool_objsize_max + STEP_SIZE) {

		alloc_factor =
			(alloc->step_pool_objsize_max + STEP_SIZE + 0.5)/
			alloc->step_pool_objsize_max;
	}
  I only moved them in memtx_engine.c with an explicit message.
3. Fix whitespaces
4. I took an example from issue to show that everything works now.
5. Fixed.


Previously, in small allocator, memory pools
were allocated at the request, which in the case
of a small slab_alloc_factor led to use
pools with incorrect sizes. This patch changed
small allocator behavior, now we allocate pools
on the stage of allocator creation. Also we use
special function to find appropriate pool, which
is faster, then previous version with rbtree.
This change fixes #5216.

Also moved a check, that the slab_alloc_factor is in
the range (1.0, 2.0] from small allocator to memtx_engine.
If factor is not in range change it to 1.0001 or 2.0 respectively

Closes #5216
---
 src/box/memtx_engine.c                  |  8 +++
 src/lib/small                           |  2 +-
 test/engine/engine.cfg                  |  3 ++
 test/engine/small_alloc_factor.lua      | 11 ++++
 test/engine/small_alloc_factor.result   | 70 +++++++++++++++++++++++++
 test/engine/small_alloc_factor.test.lua | 20 +++++++
 6 files changed, 113 insertions(+), 1 deletion(-)
 create mode 100644 test/engine/small_alloc_factor.lua
 create mode 100644 test/engine/small_alloc_factor.result
 create mode 100644 test/engine/small_alloc_factor.test.lua

diff --git a/src/box/memtx_engine.c b/src/box/memtx_engine.c
index 4f1fe3a3f..3ab292f2e 100644
--- a/src/box/memtx_engine.c
+++ b/src/box/memtx_engine.c
@@ -1116,6 +1116,14 @@ memtx_engine_new(const char *snap_dirname, bool force_recovery,
 	if (objsize_min < OBJSIZE_MIN)
 		objsize_min = OBJSIZE_MIN;
 
+	if (alloc_factor > 2) {
+		say_error("Alloc factor must be less than or equal to 2.0. It will be reduced to 2.0");
+		alloc_factor = 2.0;
+	} else if (alloc_factor <= 1.0) {
+		say_error("Alloc factor must be greater than then 1.0. It will be increased to 1.001");
+		alloc_factor = 1.001;
+	}
+
 	/* Initialize tuple allocator. */
 	quota_init(&memtx->quota, tuple_arena_max_size);
 	tuple_arena_create(&memtx->arena, &memtx->quota, tuple_arena_max_size,
diff --git a/src/lib/small b/src/lib/small
index fcac155db..2053b49df 160000
--- a/src/lib/small
+++ b/src/lib/small
@@ -1 +1 @@
-Subproject commit fcac155dba18e97b10bc668d1a2fae01184adc13
+Subproject commit 2053b49dff3cb419245d243e96dbe981625be6d2
diff --git a/test/engine/engine.cfg b/test/engine/engine.cfg
index f017a03ec..4a6a8bbbf 100644
--- a/test/engine/engine.cfg
+++ b/test/engine/engine.cfg
@@ -8,6 +8,9 @@
     },
     "gh-4973-concurrent-alter-fails.test.lua": {
         "memtx": {"engine": "memtx"}
+    },
+    "small_alloc_factor.test.lua" : {
+        "memtx": {"engine": "memtx"}
     }
 }
 
diff --git a/test/engine/small_alloc_factor.lua b/test/engine/small_alloc_factor.lua
new file mode 100644
index 000000000..a303a95d4
--- /dev/null
+++ b/test/engine/small_alloc_factor.lua
@@ -0,0 +1,11 @@
+#!/usr/bin/env tarantool
+
+require('console').listen(os.getenv('ADMIN'))
+
+box.cfg({
+    wal_mode = 'none',
+    memtx_memory = 2*1024*1024*1024,
+    listen = os.getenv("LISTEN"),
+    memtx_min_tuple_size=32,
+    slab_alloc_factor=1.03
+})
diff --git a/test/engine/small_alloc_factor.result b/test/engine/small_alloc_factor.result
new file mode 100644
index 000000000..31d0f8ffd
--- /dev/null
+++ b/test/engine/small_alloc_factor.result
@@ -0,0 +1,70 @@
+env = require('test_run')
+---
+...
+test_run = env.new()
+---
+...
+test_run:cmd('create server test with script="engine/small_alloc_factor.lua"')
+---
+- true
+...
+test_run:cmd('start server test with args="none"')
+---
+- true
+...
+test_run:cmd('switch test')
+---
+- true
+...
+s = box.schema.space.create('test')
+---
+...
+_ = s:create_index('test')
+---
+...
+function str(i) return string.rep('a', math.floor(256 * math.pow(1.03, i))) end
+---
+...
+for i=1,276 do _ = s:replace{i+200, str(i)} end
+---
+...
+for i=1,274 do _ = s:delete{i+200} end
+---
+...
+collectgarbage('collect')
+---
+- 0
+...
+_ = s:replace{200+277, str(275)}
+---
+...
+_ = s:delete{200+275}
+---
+...
+collectgarbage('collect')
+---
+- 0
+...
+_ = s:delete{200+276}
+---
+...
+collectgarbage('collect')
+---
+- 0
+...
+test_run:cmd('switch default')
+---
+- true
+...
+test_run:cmd('stop server test')
+---
+- true
+...
+test_run:cmd('cleanup server test')
+---
+- true
+...
+test_run:cmd('delete server test')
+---
+- true
+...
diff --git a/test/engine/small_alloc_factor.test.lua b/test/engine/small_alloc_factor.test.lua
new file mode 100644
index 000000000..4edc4e5c2
--- /dev/null
+++ b/test/engine/small_alloc_factor.test.lua
@@ -0,0 +1,20 @@
+env = require('test_run')
+test_run = env.new()
+test_run:cmd('create server test with script="engine/small_alloc_factor.lua"')
+test_run:cmd('start server test with args="none"')
+test_run:cmd('switch test')
+s = box.schema.space.create('test')
+_ = s:create_index('test')
+function str(i) return string.rep('a', math.floor(256 * math.pow(1.03, i))) end
+for i=1,276 do _ = s:replace{i+200, str(i)} end
+for i=1,274 do _ = s:delete{i+200} end
+collectgarbage('collect')
+_ = s:replace{200+277, str(275)}
+_ = s:delete{200+275}
+collectgarbage('collect')
+_ = s:delete{200+276}
+collectgarbage('collect')
+test_run:cmd('switch default')
+test_run:cmd('stop server test')
+test_run:cmd('cleanup server test')
+test_run:cmd('delete server test')
-- 
2.20.1

^ permalink raw reply	[flat|nested] 14+ messages in thread

* [Tarantool-patches] [PATCH v2 1/3] small: implement new size class evaluation
  2020-12-23 13:14 [Tarantool-patches] [PATCH v2 0/3] change small allocator behavior mechanik20051988
  2020-12-23 13:14 ` [Tarantool-patches] [PATCH] memtx: " mechanik20051988
@ 2020-12-23 13:14 ` mechanik20051988
  2020-12-24 15:13   ` Vladislav Shpilevoy
  2020-12-23 13:14 ` [Tarantool-patches] [PATCH v2 2/3] test: add small allocator performance test mechanik20051988
  2020-12-23 13:14 ` [Tarantool-patches] [PATCH v2 3/3] small: changed small allocator pool management mechanik20051988
  3 siblings, 1 reply; 14+ messages in thread
From: mechanik20051988 @ 2020-12-23 13:14 UTC (permalink / raw)
  To: v.shpilevoy; +Cc: tarantool-patches

From: Aleksandr Lyapunov <alyapunov@tarantool.org>

1. Fixed
2. Fixed
3. Fixed
4. Yes count of incremental size == (1 << effective_bits), for example:
   granularity = 8,
   alloc_factor = 1.05,
   min_alloc = 24
   so we have:
   ignore_bits_count = 3,
   effective_bits = 4,
   effective_size = 16,
   effective_mask = 15,
   size_shift = 16
   and we can calculate first incremental pool sizes:
   24, 32, 40, 48, ... and so on 16 times
5. Change rnd to ignore bits count
6. eff means effective, change to effective
7. For faster calculation, so as not to calculate in the process
   of calculating the offset of the pool from the beginning of the array
8. Yes, drop it
9. The user configures the allocation factor, the actual factor may differ, 
   but it depends directly on the parameter set by the user. 
   User can choose the parameter so that it suits the real allocation factor.
10. Fixed
11. Fls - find last significant bit see for example
    https://elixir.bootlin.com/linux/latest/source/arch/x86/include/asm/bitops.h#L324
12. Yes you right, it's offset in the array of pools. Rename this functions
    small_class_calc_offset_by_size and small_class_calc_size_by_offset
13. Fixed
14. You can calculate it manually using 
    float log2 = logf(2);
    sc->effective_bits = (unsigned)(logf(log2 / logf(desired_factor)) / log2 + .5);
15. Fixed
16. These are numbers from my head, i change test to make it more clear


small_alloc uses a collection of mempools of different sizes.
If small_alloc stores all mempools in an array then it have to determine
an offset in that array where the most suitable mempool is.
Let's name the offset as 'size class' and the size that the corresponding
mempool allocates as 'class size'.
Historically the class sizes grow incrementally up to some point and then
(at some size class) grow exponentially with user-provided factor.
Apart from incremental part the exponential part is not very obvious.
Binary search and floating-point logarithm could be used for size class
determination but both approaches seem to be too slow.

This patch implements faster size class evaluation based on integral
operations.

Part of #5216
---
 CMakeLists.txt                     |   4 +
 LICENSE                            |   2 +-
 small/small_class.c                |  56 ++++++++
 small/small_class.h                | 218 +++++++++++++++++++++++++++++
 test/CMakeLists.txt                |   9 ++
 test/small_class.c                 | 176 +++++++++++++++++++++++
 test/small_class.result            |  15 ++
 test/small_class_branchless.result |  15 ++
 8 files changed, 494 insertions(+), 1 deletion(-)
 create mode 100644 small/small_class.c
 create mode 100644 small/small_class.h
 create mode 100644 test/small_class.c
 create mode 100644 test/small_class.result
 create mode 100644 test/small_class_branchless.result

diff --git a/CMakeLists.txt b/CMakeLists.txt
index 4c575eb..d797128 100644
--- a/CMakeLists.txt
+++ b/CMakeLists.txt
@@ -53,6 +53,7 @@ set(lib_headers
     small/rlist.h
     small/slab_arena.h
     small/slab_cache.h
+    small/small_class.h
     small/small.h
     small/lsregion.h
     small/static.h)
@@ -63,6 +64,7 @@ set(lib_sources
     small/region.c
     small/mempool.c
     small/slab_arena.c
+    small/small_class.c
     small/small.c
     small/matras.c
     small/ibuf.c
@@ -71,6 +73,7 @@ set(lib_sources
     small/static.c)
 
 add_library(${PROJECT_NAME} STATIC ${lib_sources})
+target_link_libraries(${PROJECT_NAME} m)
 
 enable_testing()
 add_subdirectory(test)
@@ -87,6 +90,7 @@ if (NOT ENABLE_VALGRIND)
 endif()
 
 add_library(${PROJECT_NAME}_shared SHARED ${lib_sources})
+target_link_libraries(${PROJECT_NAME}_shared m)
 set_target_properties(${PROJECT_NAME}_shared PROPERTIES VERSION 1.0 SOVERSION 1)
 set_target_properties(${PROJECT_NAME}_shared PROPERTIES OUTPUT_NAME ${PROJECT_NAME})
 
 Redistribution and use in source and binary forms, with or
 without modification, are permitted provided that the following
diff --git a/small/small_class.c b/small/small_class.c
new file mode 100644
index 0000000..99915a8
--- /dev/null
+++ b/small/small_class.c
@@ -0,0 +1,56 @@
+/*
+ * Copyright 2010-2020, Tarantool AUTHORS, please see AUTHORS file.
+ *
+ * Redistribution and use in source and binary forms, with or
+ * without modification, are permitted provided that the following
+ * conditions are met:
+ *
+ * 1. Redistributions of source code must retain the above
+ *    copyright notice, this list of conditions and the
+ *    following disclaimer.
+ *
+ * 2. Redistributions in binary form must reproduce the above
+ *    copyright notice, this list of conditions and the following
+ *    disclaimer in the documentation and/or other materials
+ *    provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY <COPYRIGHT HOLDER> ``AS IS'' AND
+ * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
+ * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+ * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL
+ * <COPYRIGHT HOLDER> OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT,
+ * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
+ * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR
+ * BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
+ * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF
+ * THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
+ */
+
+#include "small_class.h"
+#include <assert.h>
+#include <math.h>
+
+void
+small_class_create(struct small_class *sc, unsigned granularity,
+		   float desired_factor, unsigned min_alloc)
+{
+	assert(granularity > 0); /* size cannot be multiple of zero. */
+	assert((granularity & (granularity - 1)) == 0); /* must power of 2. */
+	assert(desired_factor > 1.f);
+	assert(desired_factor <= 2.f);
+	assert(min_alloc > 0); /* Cannot allocate zero. */
+
+	sc->granularity = granularity;
+	sc->ignore_bits_count = __builtin_ctz(granularity);
+	float log2 = logf(2);
+	sc->effective_bits = (unsigned)(logf(log2 / logf(desired_factor)) / log2 + .5);
+	sc->effective_size = 1u << sc->effective_bits;
+	sc->effective_mask = sc->effective_size - 1u;
+	sc->size_shift = min_alloc - granularity;
+	sc->size_shift_plus_1 = sc->size_shift + 1;
+
+	sc->actual_factor = powf(2, 1.f / powf(2, sc->effective_bits));
+}
diff --git a/small/small_class.h b/small/small_class.h
new file mode 100644
index 0000000..0677557
--- /dev/null
+++ b/small/small_class.h
@@ -0,0 +1,218 @@
+#pragma once
+/*
+ * Copyright 2010-2020, Tarantool AUTHORS, please see AUTHORS file.
+ *
+ * Redistribution and use in source and binary forms, with or
+ * without modification, are permitted provided that the following
+ * conditions are met:
+ *
+ * 1. Redistributions of source code must retain the above
+ *    copyright notice, this list of conditions and the
+ *    following disclaimer.
+ *
+ * 2. Redistributions in binary form must reproduce the above
+ *    copyright notice, this list of conditions and the following
+ *    disclaimer in the documentation and/or other materials
+ *    provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY <COPYRIGHT HOLDER> ``AS IS'' AND
+ * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
+ * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+ * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL
+ * <COPYRIGHT HOLDER> OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT,
+ * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
+ * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR
+ * BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
+ * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF
+ * THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
+ */
+
+/**
+ * CHAR_BIT
+ */
+#include <limits.h>
+
+/**
+ *
+ * small_alloc uses a collection of mempools of different sizes.
+ * If small_alloc stores all mempools in an array then it have to determine
+ * an offset in that array where the most suitable mempool is.
+ * Let's name the offset as 'size class' and the size that the corresponding
+ * mempool allocates as 'class size'.
+ * Historically the class sizes grow incrementally up to some point and then
+ * (at some size class) grow exponentially with user-provided factor.
+ * Apart from incremental part the exponential part is not very obvious.
+ * Binary search and floating-point logarithm could be used for size class
+ * determination but both approaches seem to be too slow.
+ *
+ * This module is designed for faster size class determination.
+ * The idea is to use integral binary logarithm (bit search) and improve it
+ * in some way in order to increase precision - allow other logarithm bases
+ * along with 2.
+ * Binary integral logarithm is just a position of the most significant bit of
+ * a value. Let's look closer to binary representation of an allocation size
+ * and size class that is calculated as binary logarithm:
+ *       size      |  size class
+ *    00001????..  |      x
+ *    0001?????..  |    x + 1
+ *    001??????..  |    x + 2
+ * Let's take into account n lower bits just after the most significant
+ * in the value and divide size class into 2^n subclasses. For example if n = 2:
+ *       size      |  size class
+ *    0000100??..  |      x
+ *    0000101??..  |    x + 1
+ *    0000110??..  |    x + 2
+ *    0000111??..  |    x + 3
+ *    000100???..  |    x + 4  <- here the size doubles, in 4 = 2^n steps.
+ *    000101???..  |    x + 5
+ * That gives us some kind of approximation of a logarithm with a base equal
+ * to pow(2, 1 / pow(2, n)). That means that for given factor 'f' of exponent
+ * we can choose such a number of bits 'n' that gives us an approximation of
+ * an exponent that is close to 'f'.
+ *
+ * Of course if the most significant bit of a value is less than 'n' we can't
+ * use the formula above. But it's not a problem since we can (and even would
+ * like to!) use an incremental size class evaluation of those sizes.
+ *     size      |  size class
+ *    0000001    |      1  <- incremental growth.
+ *    0000010    |      2
+ *    0000011    |      3
+ *    0000100    |      4  <- here the exponential approximation starts.
+ *    0000101    |      5
+ *    0000110    |      6
+ *    0000111    |      7
+ *    000100?    |      8
+ *    000101?    |      9
+ *
+ * There's some implementation details. Size class is zero based, and the size
+ * must be rounded up to the closest class size. Even more, we want to round
+ * up size to some granularity, we doesn't want to have incremental pools of
+ * sizes 1, 2, 3.., we want them to be 8, 16, 24.... All that is achieved by
+ * subtracting size by one and omitting several lower bits of the size.
+ */
+
+#if defined(__cplusplus)
+extern "C" {
+#endif /* defined(__cplusplus) */
+
+struct small_class {
+	/** Every class size must be a multiple of this. */
+	unsigned granularity;
+	/** log2(granularity), ignore those number of the lowest bit of size. */
+	unsigned ignore_bits_count;
+	/**
+	 * A number of bits (after the most significant bit) that are used in
+	 * size class evaluation ('n' in the Explanation above).
+	 */
+	unsigned effective_bits;
+	/** 1u << effective_bits. */
+	unsigned effective_size;
+	/** effective_size - 1u. */
+	unsigned effective_mask;
+	/**
+	 * By default the lowest possible allocation size (aka class size of
+	 * class 0) is granularity. If a user wants different min_alloc, we
+	 * simply shift sizes; min_alloc = granularity + size_shift.
+	 */
+	unsigned size_shift;
+	/** Actually we need 'size_shift + 1', so store it. */
+	unsigned size_shift_plus_1;
+	/**
+	 * Exponential factor, approximation of which we managed to provide.
+	 * It is calculated from requested_factor, it's guaranteed that
+	 * it must be in range [requested_factor/k, requested_factor*k],
+	 * where k = pow(requested_factor, 0.5).
+	 */
+	float actual_factor;
+};
+
+/**
+ * Create an instance of small_class evaluator. All args must meet the
+ * requirements, undefined behaviour otherwise (at least assert).
+ * @param sc - instance to create.
+ * @param granularity - any class size will be a multiple of this value.
+ *  Must be a power of 2 (and thus greater than zero).
+ * @param desired_factor - desired factor of growth of class size.
+ *  Must be in (1, 2] range. Actual factor can be different.
+ * @param min_alloc - the lowest class size, must be greater than zero.
+ *  The good choice is the same value as granularity.
+ */
+void
+small_class_create(struct small_class *sc, unsigned granularity,
+		   float desired_factor, unsigned min_alloc);
+
+/**
+ * Find position of the most significant bit in a value.
+ * If the value is zero the behaviour is undefined.
+ */
+static inline unsigned
+small_class_fls(unsigned value)
+{
+	/*
+	 * Usually clz is implemented as bsr XOR 0x1f.
+	 * If we add another XOR the compiler will squash 'em and leave just bsr.
+	 */
+	unsigned clz = __builtin_clz(value);
+	return (sizeof(value) * CHAR_BIT - 1) ^ clz;
+}
+
+static inline unsigned
+small_class_calc_offset_by_size(struct small_class *sc, unsigned size)
+{
+	/*
+	 * Usually we have to decrement size in order to:
+	 * 1)make zero base class.
+	 * 2)round up to class size.
+	 * Also here is a good place to shift size if a user wants the lowest
+	 * class size to be different from granularity.
+	 */
+	unsigned checked_size = size - sc->size_shift_plus_1;
+	/* Check overflow. */
+	size = checked_size > size ? 0 : checked_size;
+	/* Omit never significant bits. */
+	size >>= sc->ignore_bits_count;
+#ifndef SMALL_CLASS_BRANCHLESS
+	if (size < sc->effective_size)
+		return size; /* Linear approximation, faster part. */
+	/* Get log2 base part of result. Effective bits are omitted. */
+	unsigned log2 = small_class_fls(size >> sc->effective_bits);
+#else
+	/* Evaluation without branching */
+	/*
+	 * Get log2 base part of result. Effective bits are omitted.
+	 * Also note that 1u is ORed to make log2 == 0 for smaller sizes.
+	 */
+	unsigned log2 = small_class_fls((size >> sc->effective_bits) | 1u);
+#endif
+	/* Effective bits (and leading 1?) in size, represent small steps. */
+	unsigned linear_part = size >> log2;
+	/* Log2 part, multiplied correspondingly, represent big steps. */
+	unsigned log2_part = log2 << sc->effective_bits;
+	/* Combine the result. */
+	return linear_part + log2_part;
+}
+
+static inline unsigned
+small_class_calc_size_by_offset(struct small_class *sc, unsigned cls)
+{
+	++cls;
+	/* Effective bits (without leading 1) in size */
+	unsigned linear_part = cls & sc->effective_mask;
+	/* Log2 base part of the size, maybe with leading 1 of the size. */
+	unsigned log2 = cls >> sc->effective_bits;
+	if (log2 != 0) {
+		/* Remove leading 1 from log2 part and add to linear part. */
+		log2--;
+		linear_part |= sc->effective_size;
+	}
+	/* Reassemble size and add never significant bits. */
+	return sc->size_shift + (linear_part << log2 << sc->ignore_bits_count);
+}
+
+#if defined(__cplusplus)
+} /* extern "C" { */
+#endif /* defined(__cplusplus) */
+
diff --git a/test/CMakeLists.txt b/test/CMakeLists.txt
index 8317c65..5ee0821 100644
--- a/test/CMakeLists.txt
+++ b/test/CMakeLists.txt
@@ -31,6 +31,13 @@ set_source_files_properties(rb_rand.cc PROPERTIES
 add_executable(mempool.test mempool.c)
 target_link_libraries(mempool.test small)
 
+add_executable(small_class.test small_class.c unit.c)
+target_link_libraries(small_class.test small)
+
+add_executable(small_class_branchless.test small_class.c unit.c)
+target_link_libraries(small_class_branchless.test small)
+target_compile_definitions(small_class_branchless.test PUBLIC SMALL_CLASS_BRANCHLESS)
+
 add_executable(small_alloc.test small_alloc.c)
 target_link_libraries(small_alloc.test small)
 
@@ -64,6 +71,8 @@ add_test(region ${CMAKE_CURRENT_BUILD_DIR}/region.test)
 add_test(ibuf ${CMAKE_CURRENT_BUILD_DIR}/ibuf.test)
 add_test(obuf ${CMAKE_CURRENT_BUILD_DIR}/obuf.test)
 add_test(mempool ${CMAKE_CURRENT_BUILD_DIR}/mempool.test)
+add_test(small_class ${CMAKE_CURRENT_BUILD_DIR}/small_class.test)
+add_test(small_class_branchless ${CMAKE_CURRENT_BUILD_DIR}/small_class_branchless.test)
 add_test(small_alloc ${CMAKE_CURRENT_BUILD_DIR}/small_alloc.test)
 add_test(lf_lifo ${CMAKE_CURRENT_BUILD_DIR}/lf_lifo.test)
 add_test(slab_cache ${CMAKE_CURRENT_BUILD_DIR}/slab_cache.test)
diff --git a/test/small_class.c b/test/small_class.c
new file mode 100644
index 0000000..b56cfeb
--- /dev/null
+++ b/test/small_class.c
@@ -0,0 +1,176 @@
+/*
+ * Copyright 2010-2020, Tarantool AUTHORS, please see AUTHORS file.
+ *
+ * Redistribution and use in source and binary forms, with or
+ * without modification, are permitted provided that the following
+ * conditions are met:
+ *
+ * 1. Redistributions of source code must retain the above
+ *    copyright notice, this list of conditions and the
+ *    following disclaimer.
+ *
+ * 2. Redistributions in binary form must reproduce the above
+ *    copyright notice, this list of conditions and the following
+ *    disclaimer in the documentation and/or other materials
+ *    provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY <COPYRIGHT HOLDER> ``AS IS'' AND
+ * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
+ * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+ * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL
+ * <COPYRIGHT HOLDER> OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT,
+ * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
+ * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR
+ * BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
+ * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF
+ * THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
+ */
+#include "small/small_class.h"
+#include "unit.h"
+#include <math.h>
+
+#define SZR(arr) sizeof(arr) / sizeof(arr[0])
+
+static void
+test_class(void)
+{
+	header();
+	plan(0);
+
+	struct small_class sc;
+	small_class_create(&sc, 2, 1.2, 12);
+	unsigned class = small_class_calc_offset_by_size(&sc, 0);
+	unsigned class_size = small_class_calc_size_by_offset(&sc, class);
+
+	for (unsigned size = 1; size <= 100; size++) {
+		unsigned cls = small_class_calc_offset_by_size(&sc, size);
+		if (size <= class_size)
+			fail_unless(cls == class);
+		if (size == class_size + 1) {
+			fail_unless(cls == class + 1);
+			class = cls;
+			class_size = small_class_calc_size_by_offset(&sc, class);
+		}
+	}
+
+	check_plan();
+	footer();
+}
+
+static void
+check_expectation()
+{
+	header();
+
+	const unsigned granularity_arr[] = {1, 2, 4, 8};
+	const unsigned test_sizes = 1024;
+	const unsigned test_classes = 1024;
+	/*
+	 * We expect 4 effective bits with factor = 1.05,
+	 * see small_class_create
+	 */
+	float factor = 1.05;
+	/*
+	 * 1 << 4 (effective bits mentioned above)
+	 */
+	const unsigned eff_size = 16;
+	unsigned test_class_size[test_classes + eff_size];
+
+	plan(0);
+
+	for (unsigned variant = 0; variant < SZR(granularity_arr); variant++) {
+		unsigned granularity = granularity_arr[variant];
+		unsigned min_alloc = granularity + (rand () % 16);
+
+		{
+			unsigned class_size = min_alloc - granularity;
+			/* incremental growth */
+			for (unsigned i = 0; i < eff_size; i++) {
+				class_size += granularity;
+				test_class_size[i] = class_size;
+			}
+			/* exponential growth */
+			unsigned growth = granularity;
+			for (unsigned i = eff_size; i < test_classes; i += eff_size) {
+				for (unsigned j = 0; j < eff_size; j++) {
+					class_size += growth;
+					test_class_size[i + j] = class_size;
+				}
+				growth *= 2;
+			}
+		}
+
+		struct small_class sc;
+		small_class_create(&sc, granularity, factor, min_alloc);
+		fail_unless(sc.effective_size == eff_size);
+
+		for (unsigned s = 0; s <= test_sizes; s++) {
+			unsigned expect_class = 0;
+			while (expect_class < test_classes && s > test_class_size[expect_class])
+				expect_class++;
+			unsigned expect_class_size = test_class_size[expect_class];
+			unsigned got_class = small_class_calc_offset_by_size(&sc, s);
+			unsigned got_class_size = small_class_calc_size_by_offset(&sc, got_class);
+			fail_unless(got_class == expect_class);
+			fail_unless(got_class_size == expect_class_size);
+		}
+	}
+
+	check_plan();
+	footer();
+}
+
+static void
+check_factor()
+{
+	header();
+
+	plan(0);
+
+	for (unsigned granularity = 1; granularity <= 4; granularity *= 4) {
+		for(float factor = 1.01; factor < 1.995; factor += 0.01) {
+			struct small_class sc;
+			small_class_create(&sc, granularity, factor, granularity);
+			float k = powf(factor, 0.5f);
+			fail_unless(sc.actual_factor >= factor / k && sc.actual_factor <= factor * k);
+
+			float min_deviation = 1.f;
+			float max_deviation = 1.f;
+			/* Skip incremental growth. */
+			for (unsigned i = sc.effective_size; i < sc.effective_size * 3; i++) {
+				unsigned cl_sz1 = small_class_calc_size_by_offset(&sc, i);
+				unsigned cl_sz2 = small_class_calc_size_by_offset(&sc, i + 1);
+				float real_growth = 1.f * cl_sz2 / cl_sz1;
+				float deviation = sc.actual_factor / real_growth;
+				if (deviation < min_deviation)
+					min_deviation = deviation;
+				if (deviation > max_deviation)
+					max_deviation = deviation;
+			}
+			float ln2 = logf(2);
+			fail_unless(min_deviation > ln2 && max_deviation < 2 * ln2);
+		}
+	}
+
+	check_plan();
+	footer();
+}
+
+
+int
+main(void)
+{
+	header();
+	plan(3);
+
+	test_class();
+	check_expectation();
+	check_factor();
+
+	int rc = check_plan();
+	footer();
+	return rc;
+}
diff --git a/test/small_class.result b/test/small_class.result
new file mode 100644
index 0000000..de74f00
--- /dev/null
+++ b/test/small_class.result
@@ -0,0 +1,15 @@
+	*** main ***
+1..3
+	*** test_class ***
+    1..0
+ok 1 - subtests
+	*** test_class: done ***
+	*** check_expectation ***
+    1..0
+ok 2 - subtests
+	*** check_expectation: done ***
+	*** check_factor ***
+    1..0
+ok 3 - subtests
+	*** check_factor: done ***
+	*** main: done ***
diff --git a/test/small_class_branchless.result b/test/small_class_branchless.result
new file mode 100644
index 0000000..de74f00
--- /dev/null
+++ b/test/small_class_branchless.result
@@ -0,0 +1,15 @@
+	*** main ***
+1..3
+	*** test_class ***
+    1..0
+ok 1 - subtests
+	*** test_class: done ***
+	*** check_expectation ***
+    1..0
+ok 2 - subtests
+	*** check_expectation: done ***
+	*** check_factor ***
+    1..0
+ok 3 - subtests
+	*** check_factor: done ***
+	*** main: done ***
-- 
2.20.1

^ permalink raw reply	[flat|nested] 14+ messages in thread

* [Tarantool-patches] [PATCH v2 2/3] test: add small allocator performance test
  2020-12-23 13:14 [Tarantool-patches] [PATCH v2 0/3] change small allocator behavior mechanik20051988
  2020-12-23 13:14 ` [Tarantool-patches] [PATCH] memtx: " mechanik20051988
  2020-12-23 13:14 ` [Tarantool-patches] [PATCH v2 1/3] small: implement new size class evaluation mechanik20051988
@ 2020-12-23 13:14 ` mechanik20051988
  2020-12-23 13:14 ` [Tarantool-patches] [PATCH v2 3/3] small: changed small allocator pool management mechanik20051988
  3 siblings, 0 replies; 14+ messages in thread
From: mechanik20051988 @ 2020-12-23 13:14 UTC (permalink / raw)
  To: v.shpilevoy; +Cc: mechanik20051988, tarantool-patches

From: mechanik20051988 <mechanik20.05.1988@gmail.com>

---
 CMakeLists.txt          |   1 +
 perf/.gitignore         |   1 +
 perf/CMakeLists.txt     |   7 +
 perf/small_alloc_perf.c | 375 ++++++++++++++++++++++++++++++++++++++++
 4 files changed, 384 insertions(+)
 create mode 100644 perf/.gitignore
 create mode 100644 perf/CMakeLists.txt
 create mode 100644 perf/small_alloc_perf.c

diff --git a/CMakeLists.txt b/CMakeLists.txt
index d797128..b0dec0e 100644
--- a/CMakeLists.txt
+++ b/CMakeLists.txt
@@ -77,6 +77,7 @@ target_link_libraries(${PROJECT_NAME} m)
 
 enable_testing()
 add_subdirectory(test)
+add_subdirectory(perf)
 
 if(DEFINED SMALL_EMBEDDED)
     # Don't build shared library and skip INSTALL() targets if this
diff --git a/perf/.gitignore b/perf/.gitignore
new file mode 100644
index 0000000..9ed3b07
--- /dev/null
+++ b/perf/.gitignore
@@ -0,0 +1 @@
+*.test
diff --git a/perf/CMakeLists.txt b/perf/CMakeLists.txt
new file mode 100644
index 0000000..1a9d933
--- /dev/null
+++ b/perf/CMakeLists.txt
@@ -0,0 +1,7 @@
+add_executable(small_alloc_perf.test small_alloc_perf.c)
+if (NOT ${CMAKE_SYSTEM_NAME} MATCHES "Darwin")
+  set(LIBRT "rt")
+endif ()
+
+target_link_libraries(small_alloc_perf.test small ${LIBRT})
+include_directories("${PROJECT_SOURCE_DIR}")
diff --git a/perf/small_alloc_perf.c b/perf/small_alloc_perf.c
new file mode 100644
index 0000000..3b9b443
--- /dev/null
+++ b/perf/small_alloc_perf.c
@@ -0,0 +1,375 @@
+#include <small/small.h>
+#include <small/quota.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <time.h>
+#include <math.h>
+#include "../test/unit.h"
+
+enum {
+	OBJSIZE_MIN = 3 * sizeof(int),
+	OBJECTS_MAX = 1000
+};
+
+const size_t SLAB_SIZE_MIN = 4 * 1024 * 1024;
+const size_t SLAB_SIZE_MAX = 16 * 1024 * 1024;
+static const unsigned long long NANOSEC_PER_SEC  = 1000000000;
+static const unsigned long long NANOSEC_PER_MSEC  = 1000000;
+#define SZR(arr) sizeof(arr) / sizeof(arr[0])
+
+float slab_alloc_factor[] = {1.01, 1.03, 1.05, 1.1, 1.3, 1.5};
+
+struct slab_arena arena;
+struct slab_cache cache;
+struct small_alloc alloc;
+struct quota quota;
+/** Streak type - allocating or freeing */
+bool allocating = true;
+/** Enable human output */
+bool human = false;
+/** Keep global to easily inspect the core. */
+long seed;
+char json_output[100000];
+size_t length = sizeof(json_output);
+size_t pos = 0;
+
+static int *ptrs[OBJECTS_MAX];
+
+static inline
+long long int timediff(struct timespec *tm1, struct timespec *tm2)
+{
+	return NANOSEC_PER_SEC * (tm2->tv_sec - tm1->tv_sec) +
+		(tm2->tv_nsec - tm1->tv_nsec);
+}
+
+static inline void
+free_checked(int *ptr)
+{
+	int pos = ptr[0];
+	smfree_delayed(&alloc, ptrs[pos], ptrs[pos][1]);
+	ptrs[pos] = NULL;
+}
+
+static float
+calculate_pow_factor(int size_max, int pow_max, int start)
+{
+	return exp(log((double)size_max / start) / pow_max);
+}
+
+static inline void *
+alloc_checked(int pos, int size_min, int size_max, int rnd, double pow_factor)
+{
+	int size;
+	if (ptrs[pos])
+		free_checked(ptrs[pos]);
+
+	if (!allocating)
+		return NULL;
+
+	if (rnd) {
+		size = size_min + (rand() % (size_max - size_min));
+	} else {
+		size = floor(256 * pow(pow_factor, pos));
+	}
+	ptrs[pos] = smalloc(&alloc, size);
+	if (ptrs[pos] == NULL)
+		return NULL;
+	ptrs[pos][0] = pos;
+	ptrs[pos][1] = size;
+	return ptrs[pos];
+}
+
+static int
+small_is_unused_cb(const struct mempool_stats *stats, void *arg)
+{
+	unsigned long *slab_total = arg;
+	*slab_total += stats->slabsize * stats->slabcount;
+	return 0;
+}
+
+static bool
+small_is_unused(void)
+{
+	struct small_stats totals;
+	unsigned long slab_total = 0;
+	small_stats(&alloc, &totals, small_is_unused_cb, &slab_total);
+	if (totals.used > 0)
+		return false;
+	if (slab_cache_used(&cache) > slab_total)
+		return false;
+	return true;
+}
+
+static void
+small_alloc_test(int size_min, int size_max, int iterations_max,
+	int rnd, int cnt)
+{
+	double pow_factor = calculate_pow_factor(size_max, cnt, 256);
+	for (int i = 0; i <= iterations_max; i++) {
+		int mode = i % 3;
+		switch (mode) {
+		case 1:
+			small_alloc_setopt(&alloc,
+				SMALL_DELAYED_FREE_MODE, false);
+			break;
+		case 2:
+			small_alloc_setopt(&alloc,
+				SMALL_DELAYED_FREE_MODE, true);
+			break;
+		default:
+			break;
+		}
+		for (int j = 0; j < cnt; ++j)
+			alloc_checked(j, size_min, size_max, rnd, pow_factor);
+		allocating = !allocating;
+	}
+
+	small_alloc_setopt(&alloc, SMALL_DELAYED_FREE_MODE, false);
+
+	for (int pos = 0; pos < cnt; pos++) {
+		if (ptrs[pos] != NULL)
+			free_checked(ptrs[pos]);
+	}
+
+	/* Trigger garbage collection. */
+	allocating = true;
+	for (int i = 0; i < iterations_max; i++) {
+		if (small_is_unused())
+			break;
+		void *p = alloc_checked(0, size_min, size_max, rnd, pow_factor);
+		if (p != NULL)
+			free_checked(p);
+	}
+}
+
+static void
+print_json_test_header(const char *type)
+{
+	size_t x = snprintf (json_output + pos, length,
+		"        \"%s\": {\n", type);
+	length -=x;
+	pos +=x;
+	x = snprintf (json_output + pos, length,
+		"            \"alloc factor\": {\n");
+	length -=x;
+	pos +=x;
+	for (unsigned int i = 0; i < SZR(slab_alloc_factor); i++) {
+		size_t x = snprintf (json_output + pos, length,
+			"                \"%.4f\"\n", slab_alloc_factor[i]);
+		length -=x;
+		pos +=x;
+	}
+	x = snprintf (json_output + pos, length, "            },\n");
+	length -=x;
+	pos +=x;
+	x = snprintf (json_output + pos, length,
+		"            \"time, s\": {\n");
+	length -=x;
+	pos +=x;
+}
+
+static void
+print_json_test_finish(const char * finish)
+{
+	size_t x = snprintf (json_output + pos, length, "            }\n");
+	length -=x;
+	pos +=x;
+	x = snprintf (json_output + pos, length, "        }%s\n", finish);
+	length -=x;
+	pos +=x;
+}
+
+static void
+print_json_test_result(double time)
+{
+	size_t x = snprintf (json_output + pos, length,
+		"                \"%.3f\"\n", time);
+	length -=x;
+	pos +=x;
+}
+
+static void
+small_alloc_basic(unsigned int slab_size)
+{
+	struct timespec tm1, tm2;
+	if(human) {
+		fprintf(stderr, "|              SMALL RANDOM "
+			"ALLOCATION RESULT TABLE                  |\n");
+		fprintf(stderr, "|___________________________________"
+			"_________________________________|\n");
+		fprintf(stderr, "|           alloc_factor          "
+			" |   	         time, ms            |\n");
+		fprintf(stderr, "|__________________________________|"
+			"_________________________________|\n");
+	} else {
+		print_json_test_header("random");
+	}
+	quota_init(&quota, UINT_MAX);
+	slab_arena_create(&arena, &quota, 0, slab_size, MAP_PRIVATE);
+	slab_cache_create(&cache, &arena);
+	for (unsigned int i = 0; i < SZR(slab_alloc_factor); i++) {
+		small_alloc_create(&alloc, &cache,
+			OBJSIZE_MIN, slab_alloc_factor[i]);
+		int size_min = OBJSIZE_MIN;
+		int size_max = (int)alloc.objsize_max - 1;
+		fail_unless(clock_gettime (CLOCK_MONOTONIC, &tm1) == 0);
+		small_alloc_test(size_min, size_max, 300, 1, OBJECTS_MAX);
+		fail_unless(clock_gettime (CLOCK_MONOTONIC, &tm2) == 0);
+		if (human) {
+			fprintf(stderr, "|              %.4f              |"
+				"             %6llu              |\n",
+				slab_alloc_factor[i],
+				timediff(&tm1, &tm2) / NANOSEC_PER_MSEC);
+		} else {
+			print_json_test_result(timediff(&tm1, &tm2) /
+				NANOSEC_PER_MSEC);
+		}
+		small_alloc_destroy(&alloc);
+	}
+	slab_cache_destroy(&cache);
+	slab_arena_destroy(&arena);
+	quota_init(&quota, UINT_MAX);
+	slab_arena_create(&arena, &quota, 0, slab_size, MAP_PRIVATE);
+	slab_cache_create(&cache, &arena);
+	if (human) {
+		fprintf(stderr, "|__________________________________|"
+				"_________________________________|\n");
+		fprintf(stderr, "|             SMALL EXP GROW "
+				"ALLOCATION RESULT TABLE                 |\n");
+		fprintf(stderr, "|___________________________________"
+				"_________________________________|\n");
+		fprintf(stderr, "|           alloc_factor          "
+				" |   	         time, ms            |\n");
+		fprintf(stderr, "|__________________________________|"
+				"_________________________________|\n");
+	} else {
+		print_json_test_finish(",");
+		print_json_test_header("exponent");
+	}
+	for (unsigned int i = 0; i < SZR(slab_alloc_factor); i++) {
+		small_alloc_create(&alloc, &cache,
+			OBJSIZE_MIN, slab_alloc_factor[i]);
+		int size_min = OBJSIZE_MIN;
+		int size_max = (int)alloc.objsize_max - 1;
+		fail_unless(clock_gettime (CLOCK_MONOTONIC, &tm1) == 0);
+		small_alloc_test(size_min, size_max, 1000, 0, OBJECTS_MAX);
+		fail_unless(clock_gettime (CLOCK_MONOTONIC, &tm2) == 0);
+		if (human) {
+			fprintf(stderr, "|              %.4f              |"
+				"             %6llu              |\n",
+				slab_alloc_factor[i],
+				timediff(&tm1, &tm2) / NANOSEC_PER_MSEC);
+		} else {
+			print_json_test_result(timediff(&tm1, &tm2) /
+				NANOSEC_PER_MSEC);
+		}
+		small_alloc_destroy(&alloc);
+	}
+	if (human) {
+		fprintf(stderr, "|___________________________________"
+				"_________________________________|\n");
+	} else {
+		print_json_test_finish(",");
+	}
+	slab_cache_destroy(&cache);
+	slab_arena_destroy(&arena);
+}
+
+static void
+small_alloc_large()
+{
+	struct timespec tm1, tm2;
+	size_t large_size_min = mempool_objsize_max(cache.arena->slab_size);
+	size_t large_size_max = 2 * cache.arena->slab_size;
+	if (human) {
+		fprintf(stderr, "|              LARGE RANDOM "
+				"ALLOCATION RESULT TABLE                  |\n");
+		fprintf(stderr, "|___________________________________"
+				"_________________________________|\n");
+		fprintf(stderr, "|           alloc_factor          "
+				" |   	         time, ms            |\n");
+		fprintf(stderr, "|__________________________________|"
+				"_________________________________|\n");
+	} else {
+		print_json_test_header("large");
+	}
+	for (unsigned int i = 0; i < SZR(slab_alloc_factor); i++) {
+		small_alloc_create(&alloc, &cache, OBJSIZE_MIN,
+			slab_alloc_factor[i]);
+		fail_unless(clock_gettime (CLOCK_MONOTONIC, &tm1) == 0);
+		small_alloc_test(large_size_min, large_size_max, 200, 1, 25);
+		fail_unless(clock_gettime (CLOCK_MONOTONIC, &tm2) == 0);
+		if (human) {
+			fprintf(stderr, "|              %.4f              |"
+					"             %6llu              |\n",
+					slab_alloc_factor[i],
+					timediff(&tm1, &tm2) / NANOSEC_PER_MSEC);
+		} else {
+			print_json_test_result(timediff(&tm1, &tm2) /
+				NANOSEC_PER_MSEC);
+		}
+		small_alloc_destroy(&alloc);
+	}
+	if (human) {
+		fprintf(stderr, "|___________________________________"
+				"_________________________________|\n");
+	} else {
+		print_json_test_finish("");
+	}
+}
+
+int main(int argc, char* argv[])
+{
+	size_t x;
+	seed = time(0);
+	srand(seed);
+
+	if (argc == 2 && !strcmp(argv[1], "-h")) //human clear output
+		human = true;
+
+	if (!human) {
+		x = snprintf (json_output + pos, length, "{\n");
+		length -=x;
+		pos +=x;
+	}
+	for (unsigned int slab_size = SLAB_SIZE_MIN; slab_size <= SLAB_SIZE_MAX;
+	     slab_size *= 2) {
+		if(human) {
+			fprintf(stderr, "_____________________________________"
+					"_________________________________\n");
+			fprintf(stderr, "|           PERFORMANCE TEST WITH SLABSIZE "
+					"%8u BYTES            |\n", slab_size);
+			fprintf(stderr, "|___________________________________"
+					"_________________________________|\n");
+		} else {
+			size_t x = snprintf (json_output + pos, length,
+				"    \"test\": {\n");
+			length -=x;
+			pos +=x;
+			x = snprintf (json_output + pos, length,
+				"        \"slab size, bytes\": \"%u\",\n",
+				slab_size);
+			length -=x;
+			pos +=x;
+		}
+		small_alloc_basic(slab_size);
+		quota_init(&quota, UINT_MAX);
+		slab_arena_create(&arena, &quota, 0, slab_size, MAP_PRIVATE);
+		slab_cache_create(&cache, &arena);
+		small_alloc_large();
+		slab_cache_destroy(&cache);
+		slab_arena_destroy(&arena);
+		if (!human) {
+			x = snprintf (json_output + pos, length,
+				"    }%s\n",
+				(slab_size == SLAB_SIZE_MAX ? "" : ","));
+			length -=x;
+			pos +=x;
+		}
+	}
+	if (!human) {
+		x = snprintf (json_output + pos, length, "}\n");
+		fprintf(stderr, "%s\n", json_output);
+	}
+	return EXIT_SUCCESS;
+}
-- 
2.20.1

^ permalink raw reply	[flat|nested] 14+ messages in thread

* [Tarantool-patches] [PATCH v2 3/3] small: changed small allocator pool management
  2020-12-23 13:14 [Tarantool-patches] [PATCH v2 0/3] change small allocator behavior mechanik20051988
                   ` (2 preceding siblings ...)
  2020-12-23 13:14 ` [Tarantool-patches] [PATCH v2 2/3] test: add small allocator performance test mechanik20051988
@ 2020-12-23 13:14 ` mechanik20051988
  2020-12-24 15:13   ` Vladislav Shpilevoy
  3 siblings, 1 reply; 14+ messages in thread
From: mechanik20051988 @ 2020-12-23 13:14 UTC (permalink / raw)
  To: v.shpilevoy; +Cc: tarantool-patches

1. Fxed
2. As i understand you comment, you wrote that pools 
   should be aligned on the 8-byte boundary. 
   This is guaranteed by the granularity parameter in small_class if min_alloc
   have 8-byte boundary alignment. We calculate 
   min_alloc = objsize_min = small_align(objsize_min, sizeof(intptr_t));
   and pass granularity sizeof(uintptr_t).
3. Fixed
4. Fixed

In previous version allocator created new pool if necessary
and inserted it in the pools tree. Now we allocate pools on
the stage of allocator creation according alloc_factor.
We use small_alloc class for this purpose also we use it
to find necessary pool when we alloc memory. This is faster
then previous allocator behavior and also fixes #5216.

Closes #5216
---
 small/small.c | 216 ++++++++++++--------------------------------------
 small/small.h |  47 ++++-------
 2 files changed, 66 insertions(+), 197 deletions(-)

diff --git a/small/small.c b/small/small.c
index 48085fb..d3c51b8 100644
--- a/small/small.c
+++ b/small/small.c
@@ -33,66 +33,34 @@
 #include <string.h>
 #include <stdio.h>
 
-enum {
-	/** Step size for stepped pools, in bytes */
-	STEP_SIZE = 8,
-	/**
-	 * LB stands for logarithm with binary base, this constant
-	 * is used for bit shifts, when we need to divide by
-	 * STEP_SIZE.
-	 */
-	STEP_SIZE_LB = 3,
-};
-
-rb_proto(, factor_tree_, factor_tree_t, struct factor_pool)
-
-/** Used for search in the tree. */
-static inline int
-factor_pool_cmp(const struct factor_pool *a, const struct factor_pool *b)
+static inline struct factor_pool *
+factor_pool_search(struct small_alloc *alloc, size_t size)
 {
-	return a->pool.objsize > b->pool.objsize ? 1 :
-		a->pool.objsize < b->pool.objsize ? -1 : 0;
+	if (size > alloc->objsize_max)
+		return NULL;
+	unsigned cls = small_class_calc_offset_by_size(&alloc->small_class, size);
+	struct factor_pool *pool = &alloc->factor_pool_cache[cls];
+	return pool;
 }
 
-rb_gen(, factor_tree_, factor_tree_t, struct factor_pool, node,
-       factor_pool_cmp)
-
-static inline struct factor_pool *
-factor_pool_create(struct small_alloc *alloc,
-		   struct factor_pool *upper_bound,
-		   size_t size)
+static inline void
+factor_pool_create(struct small_alloc *alloc)
 {
-	assert(size > alloc->step_pool_objsize_max);
-	assert(size <= alloc->objsize_max);
-
-	if (alloc->factor_pool_next == NULL) {
-		/**
-		 * Too many factored pools already, fall back
-		 * to an imperfect one.
-		 */
-		return upper_bound;
+	size_t objsize = 0;
+	for (alloc->factor_pool_cache_size = 0;
+	     objsize < alloc->objsize_max && alloc->factor_pool_cache_size < FACTOR_POOL_MAX;
+	     alloc->factor_pool_cache_size++) {
+		size_t prevsize = objsize;
+		objsize = small_class_calc_size_by_offset(&alloc->small_class,
+			alloc->factor_pool_cache_size);
+		if (objsize > alloc->objsize_max)
+			objsize = alloc->objsize_max;
+		struct factor_pool *pool =
+			&alloc->factor_pool_cache[alloc->factor_pool_cache_size];
+		mempool_create(&pool->pool, alloc->cache, objsize);
+		pool->objsize_min = prevsize + 1;
 	}
-	size_t objsize = alloc->step_pool_objsize_max;
-	size_t prevsize;
-	do {
-		prevsize = objsize;
-		/*
-		 * Align objsize after each multiplication to
-		 * ensure that the distance between objsizes of
-		 * factored pools is a multiple of STEP_SIZE.
-		 */
-		objsize = small_align(objsize * alloc->factor,
-				      sizeof(intptr_t));
-		assert(objsize > alloc->step_pool_objsize_max);
-	} while (objsize < size);
-	if (objsize > alloc->objsize_max)
-		objsize = alloc->objsize_max;
-	struct factor_pool *pool = alloc->factor_pool_next;
-	alloc->factor_pool_next = pool->next;
-	mempool_create(&pool->pool, alloc->cache, objsize);
-	pool->objsize_min = prevsize + 1;
-	factor_tree_insert(&alloc->factor_pools, pool);
-	return pool;
+	alloc->objsize_max = objsize;
 }
 
 /** Initialize the small allocator. */
@@ -102,53 +70,21 @@ small_alloc_create(struct small_alloc *alloc, struct slab_cache *cache,
 {
 	alloc->cache = cache;
 	/* Align sizes. */
-	objsize_min = small_align(objsize_min, STEP_SIZE);
-	alloc->step_pool0_step_count = (objsize_min - 1) >> STEP_SIZE_LB;
+	objsize_min = small_align(objsize_min, sizeof(intptr_t));
 	/* Make sure at least 4 largest objects can fit in a slab. */
 	alloc->objsize_max =
 		mempool_objsize_max(slab_order_size(cache, cache->order_max));
 
-	if (!(alloc->objsize_max > objsize_min + STEP_POOL_MAX * STEP_SIZE)) {
-		fprintf(stderr, "Can't create small alloc, small "
-			"object min size should not be greather than %u\n",
-			alloc->objsize_max - (STEP_POOL_MAX + 1) * STEP_SIZE);
-		abort();
-	}
+	assert(alloc_factor > 1. && alloc_factor <= 2.);
 
-	struct mempool *step_pool;
-	for (step_pool = alloc->step_pools;
-	     step_pool < alloc->step_pools + STEP_POOL_MAX;
-	     step_pool++) {
-		mempool_create(step_pool, alloc->cache, objsize_min);
-		objsize_min += STEP_SIZE;
-	}
-	alloc->step_pool_objsize_max = (step_pool - 1)->objsize;
-	if (alloc_factor > 2.0)
-		alloc_factor = 2.0;
+	alloc->factor = alloc_factor;
 	/*
-	 * Correct the user-supplied alloc_factor to ensure that
-	 * it actually produces growing object sizes.
+	 * Second parameter (uintptr_t) - granularity,
+	 * determines alignment.
 	 */
-	if (alloc->step_pool_objsize_max * alloc_factor <
-	    alloc->step_pool_objsize_max + STEP_SIZE) {
-
-		alloc_factor =
-			(alloc->step_pool_objsize_max + STEP_SIZE + 0.5)/
-			alloc->step_pool_objsize_max;
-	}
-	alloc->factor = alloc_factor;
-
-	/* Initialize the factored pool cache. */
-	struct factor_pool *factor_pool = alloc->factor_pool_cache;
-	do {
-		factor_pool->next = factor_pool + 1;
-		factor_pool++;
-	} while (factor_pool !=
-		 alloc->factor_pool_cache + FACTOR_POOL_MAX - 1);
-	factor_pool->next = NULL;
-	alloc->factor_pool_next = alloc->factor_pool_cache;
-	factor_tree_new(&alloc->factor_pools);
-	(void) factor_pool_create(alloc, NULL, alloc->objsize_max);
+	small_class_create(&alloc->small_class, sizeof(intptr_t),
+		alloc->factor, objsize_min);
+	factor_pool_create(alloc);
 
 	lifo_init(&alloc->delayed);
 	lifo_init(&alloc->delayed_large);
@@ -225,72 +161,27 @@ smalloc(struct small_alloc *alloc, size_t size)
 {
 	small_collect_garbage(alloc);
 
-	struct mempool *pool;
-	int idx = (size - 1) >> STEP_SIZE_LB;
-	idx = (idx > (int) alloc->step_pool0_step_count) ? idx - alloc->step_pool0_step_count : 0;
-	if (idx < STEP_POOL_MAX) {
-		/* Allocate in a stepped pool. */
-		pool = &alloc->step_pools[idx];
-		assert(size <= pool->objsize &&
-		       (size + STEP_SIZE > pool->objsize || idx == 0));
-	} else {
-		struct factor_pool pattern;
-		pattern.pool.objsize = size;
-		struct factor_pool *upper_bound =
-			factor_tree_nsearch(&alloc->factor_pools, &pattern);
-		if (upper_bound == NULL) {
-			/* Object is too large, fallback to slab_cache */
-			struct slab *slab = slab_get_large(alloc->cache, size);
-			if (slab == NULL)
-				return NULL;
-			return slab_data(slab);
-		}
-
-		if (size < upper_bound->objsize_min)
-			upper_bound = factor_pool_create(alloc, upper_bound,
-							 size);
-		pool = &upper_bound->pool;
+	struct factor_pool *upper_bound = factor_pool_search(alloc, size);
+	if (upper_bound == NULL) {
+		/* Object is too large, fallback to slab_cache */
+		struct slab *slab = slab_get_large(alloc->cache, size);
+		if (slab == NULL)
+			return NULL;
+		return slab_data(slab);
 	}
+	struct mempool *pool = &upper_bound->pool;
 	assert(size <= pool->objsize);
 	return mempool_alloc(pool);
 }
 
-static void
-small_recycle_pool(struct small_alloc *alloc, struct mempool *pool)
-{
-	if (mempool_used(pool) == 0 &&
-	    pool->objsize > alloc->step_pool_objsize_max &&
-	    alloc->factor_pool_next == NULL) {
-		struct factor_pool *factor_pool = (struct factor_pool *)
-			((char *) pool - (intptr_t)
-			 &((struct factor_pool *) NULL)->pool);
-		factor_tree_remove(&alloc->factor_pools, factor_pool);
-		mempool_destroy(pool);
-		alloc->factor_pool_next = factor_pool;
-	}
-}
-
 static inline struct mempool *
 mempool_find(struct small_alloc *alloc, size_t size)
 {
-	struct mempool *pool;
-	int idx = (size - 1) >> STEP_SIZE_LB;
-	idx = (idx > (int) alloc->step_pool0_step_count) ? idx - alloc->step_pool0_step_count : 0;
-	if (idx < STEP_POOL_MAX) {
-		/* Allocated in a stepped pool. */
-			pool = &alloc->step_pools[idx];
-			assert((size + STEP_SIZE > pool->objsize) || (idx == 0));
-	} else {
-		/* Allocated in a factor pool. */
-		struct factor_pool pattern;
-		pattern.pool.objsize = size;
-		struct factor_pool *upper_bound =
-			factor_tree_nsearch(&alloc->factor_pools, &pattern);
-		if (upper_bound == NULL)
-			return NULL; /* Allocated by slab_cache. */
-		assert(size >= upper_bound->objsize_min);
-		pool = &upper_bound->pool;
-	}
+	struct factor_pool *upper_bound = factor_pool_search(alloc, size);
+	if (upper_bound == NULL)
+		return NULL; /* Allocated by slab_cache. */
+	assert(size >= upper_bound->objsize_min);
+	struct mempool *pool = &upper_bound->pool;
 	assert(size <= pool->objsize);
 	return pool;
 }
@@ -319,8 +210,6 @@ smfree(struct small_alloc *alloc, void *ptr, size_t size)
 
 	/* Regular allocation in mempools */
 	mempool_free(pool, ptr);
-	if (mempool_used(pool) == 0)
-		small_recycle_pool(alloc, pool);
 }
 
 /**
@@ -351,8 +240,7 @@ smfree_delayed(struct small_alloc *alloc, void *ptr, size_t size)
 struct mempool_iterator
 {
 	struct small_alloc *alloc;
-	struct mempool *step_pool;
-	struct factor_tree_iterator factor_iterator;
+	uint32_t factor_iterator;
 };
 
 void
@@ -360,19 +248,19 @@ mempool_iterator_create(struct mempool_iterator *it,
 			struct small_alloc *alloc)
 {
 	it->alloc = alloc;
-	it->step_pool = alloc->step_pools;
-	factor_tree_ifirst(&alloc->factor_pools, &it->factor_iterator);
+	it->factor_iterator = 0;
 }
 
 struct mempool *
 mempool_iterator_next(struct mempool_iterator *it)
 {
-	if (it->step_pool < it->alloc->step_pools + STEP_POOL_MAX)
-		return it->step_pool++;
-	struct factor_pool *factor_pool = factor_tree_inext(&it->factor_iterator);
-	if (factor_pool) {
+	struct factor_pool *factor_pool = NULL;
+	if (it->factor_iterator < it->alloc->factor_pool_cache_size)
+		factor_pool =
+			&it->alloc->factor_pool_cache[(it->factor_iterator)++];
+	if (factor_pool)
 		return &(factor_pool->pool);
-	}
+
 	return NULL;
 }
 
diff --git a/small/small.h b/small/small.h
index 376c600..02d42d3 100644
--- a/small/small.h
+++ b/small/small.h
@@ -34,6 +34,7 @@
 #include "mempool.h"
 #include "slab_arena.h"
 #include "lifo.h"
+#include "small_class.h"
 
 #if defined(__cplusplus)
 extern "C" {
@@ -86,10 +87,8 @@ extern "C" {
 
 /** Basic constants of small object allocator. */
 enum {
-	/** How many stepped pools there is. */
-	STEP_POOL_MAX = 32,
 	/** How many factored pools there can be. */
-	FACTOR_POOL_MAX = 256,
+	FACTOR_POOL_MAX = 1024,
 };
 
 enum small_opt {
@@ -107,8 +106,6 @@ enum small_opt {
  */
 struct factor_pool
 {
-	/** rb_tree entry */
-	rb_node(struct factor_pool) node;
 	/** the pool itself. */
 	struct mempool pool;
 	/**
@@ -117,12 +114,8 @@ struct factor_pool
 	 * pool.
 	 */
 	size_t objsize_min;
-	/** next free factor pool in the cache. */
-	struct factor_pool *next;
 };
 
-typedef rb_tree(struct factor_pool) factor_tree_t;
-
 /**
  * Free mode
  */
@@ -138,26 +131,10 @@ enum small_free_mode {
 /** A slab allocator for a wide range of object sizes. */
 struct small_alloc {
 	struct slab_cache *cache;
-	uint32_t step_pool_objsize_max;
-	/**
-	 * All slabs in all pools must be of the same order,
-	 * otherwise small_free() has no way to derive from
-	 * pointer its slab and then the pool.
-	 */
-	/**
-	 * An array of "stepped" pools, pool->objsize of adjacent
-	 * pools differ by a fixed size (step).
-	 */
-	struct mempool step_pools[STEP_POOL_MAX];
 	/** A cache for nodes in the factor_pools tree. */
 	struct factor_pool factor_pool_cache[FACTOR_POOL_MAX];
-	/** First free element in factor_pool_cache. */
-	struct factor_pool *factor_pool_next;
-	/**
-	 * A red-black tree with "factored" pools, i.e.
-	 * each pool differs from its neighbor by a factor.
-	 */
-	factor_tree_t factor_pools;
+	/* factor_pool_cache array real size */
+	uint32_t factor_pool_cache_size;
 	/**
 	 * List of mempool which objects to be freed if delayed free mode.
 	 */
@@ -171,19 +148,23 @@ struct small_alloc {
 	 * Is provided during initialization.
 	 */
 	float factor;
+	/** Small class for this allocator */
+	struct small_class small_class;
 	uint32_t objsize_max;
 	/**
 	 * Free mode.
 	 */
 	enum small_free_mode free_mode;
-	/**
-	 * Object size of step pool 0 divided by STEP_SIZE, to
-	 * quickly find the right stepped pool given object size.
-	 */
-	uint32_t step_pool0_step_count;
 };
 
-/** Initialize a small memory allocator. */
+/**
+ * Initialize a small memory allocator.
+ * @param alloc - instance to create.
+ * @param cache - pointer to used slab cache.
+ * @param objsize_min - minimal object size.
+ * @param alloc_factor - desired factor of growth object size.
+ * Must be in (1, 2] range.
+ */
 void
 small_alloc_create(struct small_alloc *alloc, struct slab_cache *cache,
 		   uint32_t objsize_min, float alloc_factor);
-- 
2.20.1

^ permalink raw reply	[flat|nested] 14+ messages in thread

* Re: [Tarantool-patches] [PATCH] memtx: change small allocator behavior
  2020-12-23 13:14 ` [Tarantool-patches] [PATCH] memtx: " mechanik20051988
@ 2020-12-24 15:13   ` Vladislav Shpilevoy
       [not found]     ` <0076A088-8CBC-4238-9EEB-0C73EC516098@hxcore.ol>
  0 siblings, 1 reply; 14+ messages in thread
From: Vladislav Shpilevoy @ 2020-12-24 15:13 UTC (permalink / raw)
  To: mechanik20051988; +Cc: tarantool-patches

Hi! Thanks for the fixes!

On 23.12.2020 14:14, mechanik20051988 via Tarantool-patches wrote:
> From: mechanik20051988 <mechanik20.05.1988@gmail.com>
> 
> Branch: https://github.com/tarantool/tarantool/tree/mechanik20051988/gh-5216-fix-strange-allocator-behavior
> Pull request: https://github.com/tarantool/tarantool/pull/5503
> 
> Thank you for the previous review. Here some answers on you questions.

I don't remember the questions by their numbers. I enumerate them so as
people wouldn't miss any of the comments. For example, when I say 'see 10
comments below', it is supposed to be easier to check if you didn't miss,
say, comment 5, between comments 4 and 6.

Try to follow this guide:
https://github.com/tarantool/tarantool/wiki/Code-review-procedure#during-the-review

Responses better be right under the questions, in response to the original
email in the old thread, with diff under each comment.

> 2. As you can see at this moment, small_alloc_create already 
>    has restrictions on alloc_factor (see small.c in master branch)
>    They change it silently. 
>    if (alloc_factor > 2.0)
> 		alloc_factor = 2.0;
>    /*
>     * Correct the user-supplied alloc_factor to ensure that
>     * it actually produces growing object sizes.
>     */
>    if (alloc->step_pool_objsize_max * alloc_factor <
> 	   alloc->step_pool_objsize_max + STEP_SIZE) {
> 
> 		alloc_factor =
> 			(alloc->step_pool_objsize_max + STEP_SIZE + 0.5)/
> 			alloc->step_pool_objsize_max;
> 	}
>   I only moved them in memtx_engine.c with an explicit message.

Ok, I see now.

See 3 comments below.

>  src/box/memtx_engine.c                  |  8 +++
>  src/lib/small                           |  2 +-
>  test/engine/engine.cfg                  |  3 ++
>  test/engine/small_alloc_factor.lua      | 11 ++++
>  test/engine/small_alloc_factor.result   | 70 +++++++++++++++++++++++++
>  test/engine/small_alloc_factor.test.lua | 20 +++++++
>  6 files changed, 113 insertions(+), 1 deletion(-)
>  create mode 100644 test/engine/small_alloc_factor.lua
>  create mode 100644 test/engine/small_alloc_factor.result
>  create mode 100644 test/engine/small_alloc_factor.test.lua
> 
> diff --git a/src/box/memtx_engine.c b/src/box/memtx_engine.c
> index 4f1fe3a3f..3ab292f2e 100644
> --- a/src/box/memtx_engine.c
> +++ b/src/box/memtx_engine.c
> @@ -1116,6 +1116,14 @@ memtx_engine_new(const char *snap_dirname, bool force_recovery,
>  	if (objsize_min < OBJSIZE_MIN)
>  		objsize_min = OBJSIZE_MIN;
>  
> +	if (alloc_factor > 2) {
> +		say_error("Alloc factor must be less than or equal to 2.0. It will be reduced to 2.0");
> +		alloc_factor = 2.0;
> +	} else if (alloc_factor <= 1.0) {
> +		say_error("Alloc factor must be greater than then 1.0. It will be increased to 1.001");

1. Can't parse 'than then' - please, rephrase. I assume 'then' is
not needed.

> +		alloc_factor = 1.001;

2. I don't see the factor being rounded up in the original code.
Why did you add it? And why 1.0 is bad?

> +	}
> diff --git a/test/engine/small_alloc_factor.result b/test/engine/small_alloc_factor.result
> new file mode 100644
> index 000000000..31d0f8ffd
> --- /dev/null
> +++ b/test/engine/small_alloc_factor.result

3. Please, read this document, and especially the specified
section: https://github.com/tarantool/tarantool/wiki/Code-review-procedure#testing.
The test file names should have a special pattern. Please, follow it.

^ permalink raw reply	[flat|nested] 14+ messages in thread

* Re: [Tarantool-patches] [PATCH v2 1/3] small: implement new size class evaluation
  2020-12-23 13:14 ` [Tarantool-patches] [PATCH v2 1/3] small: implement new size class evaluation mechanik20051988
@ 2020-12-24 15:13   ` Vladislav Shpilevoy
       [not found]     ` <A90D94B7-298A-4D1B-8134-6EE2ED45D615@hxcore.ol>
  2020-12-28 12:10     ` [Tarantool-patches] " Vladislav Shpilevoy
  0 siblings, 2 replies; 14+ messages in thread
From: Vladislav Shpilevoy @ 2020-12-24 15:13 UTC (permalink / raw)
  To: mechanik20051988; +Cc: tarantool-patches

Thanks for the fixes!

>> Lets omit unnecessary changes. This clearly has nothing to do with
>> the functional part of the patch.
> 1. Fixed

Nope, it is not. The diff hunk is still here.

>> I don't understand. So you can make the factor smaller than it was
>> requested? What is the point in configuring the factor then?
> 9. The user configures the allocation factor, the actual factor may differ, 
>    but it depends directly on the parameter set by the user. 
>    User can choose the parameter so that it suits the real allocation factor.

But this is not the answer on the question, is it? What is the point is
making it bigger if it can get smaller in the result? And the user can't
even understand how to select the factor he actually needs. For instance,
he sets 1.5, but he has no idea what will be the final value. How can one
tune it then? How to choose the value?

> diff --git a/small/small_class.h b/small/small_class.h
> new file mode 100644
> index 0000000..0677557
> --- /dev/null
> +++ b/small/small_class.h
> @@ -0,0 +1,218 @@
> +
> +/**
> + * CHAR_BIT
> + */
> +#include <limits.h>
> +
> +/**
> + *

Unnecessary empty line.

> + * small_alloc uses a collection of mempools of different sizes.
> + * If small_alloc stores all mempools in an array then it have to determine
> + * an offset in that array where the most suitable mempool is.
> + * Let's name the offset as 'size class' and the size that the corresponding
> + * mempool allocates as 'class size'.> diff --git a/test/small_class.c b/test/small_class.c
> new file mode 100644
> index 0000000..b56cfeb
> --- /dev/null
> +++ b/test/small_class.c
> @@ -0,0 +1,176 @@
> +#include "small/small_class.h"
> +#include "unit.h"
> +#include <math.h>
> +
> +#define SZR(arr) sizeof(arr) / sizeof(arr[0])

We have lengthof() in trivia/util.h.

The test below I still don't understand in a single bit :D
But I give up, and hope Alexander L. validated all the calculations
and ensured they don't make things slower.

^ permalink raw reply	[flat|nested] 14+ messages in thread

* Re: [Tarantool-patches] [PATCH v2 3/3] small: changed small allocator pool management
  2020-12-23 13:14 ` [Tarantool-patches] [PATCH v2 3/3] small: changed small allocator pool management mechanik20051988
@ 2020-12-24 15:13   ` Vladislav Shpilevoy
       [not found]     ` <27E47303-4307-4713-BB8A-2427FED09DDE@hxcore.ol>
  0 siblings, 1 reply; 14+ messages in thread
From: Vladislav Shpilevoy @ 2020-12-24 15:13 UTC (permalink / raw)
  To: mechanik20051988; +Cc: tarantool-patches

Thanks for the fixes!

On 23.12.2020 14:14, mechanik20051988 wrote:
> 1. Fxed
> 2. As i understand you comment, you wrote that pools 
>    should be aligned on the 8-byte boundary. 
>    This is guaranteed by the granularity parameter in small_class if min_alloc
>    have 8-byte boundary alignment. We calculate 
>    min_alloc = objsize_min = small_align(objsize_min, sizeof(intptr_t));
>    and pass granularity sizeof(uintptr_t).

No, I meant the indentation alignment is broken. If a
function call consists of multiple lines, the non-first
lines should be aligned by '(' + 1. See examples in
the existing code.

^ permalink raw reply	[flat|nested] 14+ messages in thread

* Re: [Tarantool-patches] FW:  [PATCH] memtx: change small allocator behavior
       [not found]     ` <0076A088-8CBC-4238-9EEB-0C73EC516098@hxcore.ol>
@ 2020-12-25  7:42       ` Evgeny Mekhanik
  2020-12-28 12:10         ` Vladislav Shpilevoy
  0 siblings, 1 reply; 14+ messages in thread
From: Evgeny Mekhanik @ 2020-12-25  7:42 UTC (permalink / raw)
  To: Vladislav Shpilevoy; +Cc: tarantool-patches

[-- Attachment #1: Type: text/plain, Size: 6520 bytes --]


Hi, thank you for review.I answer your questions below.
 
See 3 comments below.
 
>  src/box/memtx_engine.c                  |  8 +++
>  src/lib/small                           |  2 +-
>  test/engine/engine.cfg                  |  3 ++
>  test/engine/small_alloc_factor.lua      | 11 ++++
>  test/engine/small_alloc_factor.result   | 70 +++++++++++++++++++++++++
>  test/engine/small_alloc_factor.test.lua | 20 +++++++
>  6 files changed, 113 insertions(+), 1 deletion(-)
>  create mode 100644 test/engine/small_alloc_factor.lua
>  create mode 100644 test/engine/small_alloc_factor.result
>  create mode 100644 test/engine/small_alloc_factor.test.lua
>
> diff --git a/src/box/memtx_engine.c b/src/box/memtx_engine.c
> index 4f1fe3a3f..3ab292f2e 100644
> --- a/src/box/memtx_engine.c
> +++ b/src/box/memtx_engine.c
> @@ -1116,6 +1116,14 @@ memtx_engine_new(const char *snap_dirname, bool force_recovery,
>        if (objsize_min < OBJSIZE_MIN)
>                   objsize_min = OBJSIZE_MIN;
> 
> +     if (alloc_factor > 2) {
> +                say_error("Alloc factor must be less than or equal to 2.0. It will be reduced to 2.0");
> +                alloc_factor = 2.0;
> +     } else if (alloc_factor <= 1.0) {
> +                say_error("Alloc factor must be greater than then 1.0. It will be increased to 1.001");
 
1. Can't parse 'than then' - please, rephrase. I assume 'then' is
not needed.
 
Fixed incorrect message, now:
 
+    if (alloc_factor > 2) {
+        say_error("Alloc factor must be less than or equal to 2.0. It will be reduced to 2.0");
+        alloc_factor = 2.0;
+    } else if (alloc_factor <= 1.0) {
+        say_error("Alloc factor must be greater than 1.0. It will be increased to 1.001");
+        alloc_factor = 1.001;
+    }
+
 
> +                alloc_factor = 1.001;
 
2. I don't see the factor being rounded up in the original code.
Why did you add it? And why 1.0 is bad?
 
Answer:
 
Here is a code which rounded up alloc factor in master branch.
    /*
     * Correct the user-supplied alloc_factor to ensure that
     * it actually produces growing object sizes.
     */
    if (alloc->step_pool_objsize_max * alloc_factor <
        alloc->step_pool_objsize_max + STEP_SIZE) {
        alloc_factor =
            (alloc->step_pool_objsize_max + STEP_SIZE + 0.5)/
            alloc->step_pool_objsize_max;
    }
    I use gdb to show it:
    tarantool> box.cfg{slab_alloc_factor = 1.01}
    2020-12-24 19:22:33.416 [22602] main/103/interactive C> Tarantool 2.7.0-148-gd5a5754a3
    2020-12-24 19:22:33.416 [22602] main/103/interactive C> log level 5
    2020-12-24 19:22:33.416 [22602] main/103/interactive I> mapping 268435456 bytes for memtx tuple arena...
    Breakpoint 1, small_alloc_create (alloc=0x555555cfe788, cache=0x555555cfe530, objsize_min=272,
                          alloc_factor=1.00999999) at /home/evgeny/MASTER/tarantool/src/lib/small/small/small.c:135
    135                     alloc_factor =
    (gdb) n
    139             alloc->factor = alloc_factor;
    (gdb) p alloc_factor
    $1 = 1.032197
    (gdb)
    As you can see if you pass slab_alloc_factor < 1.03 it's changed to 1.03. I try 0.01 factor and get the same value.
    It's code from master branch, now user can pass >= 1.001 factor. We can't use 1.0, because we need increment to pool size.
 
> +     }
> diff --git a/test/engine/small_alloc_factor.result b/test/engine/small_alloc_factor.result
> new file mode 100644
> index 000000000..31d0f8ffd
> --- /dev/null
> +++ b/test/engine/small_alloc_factor.result
 
3. Please, read this document, and especially the specified
section:  https://github.com/tarantool/tarantool/wiki/Code-review-procedure#testing .
The test file names should have a special pattern. Please, follow it.
 
Rename test, add necessary gh-5216 (issue number) prefix
diff --git a/test/engine/gh-5216-small_alloc_factor.lua b/test/engine/gh-5216-small_alloc_factor.lua
+#!/usr/bin/env tarantool
+
+require('console').listen(os.getenv('ADMIN'))
+
+box.cfg({
+    wal_mode = 'none',
+    memtx_memory = 2*1024*1024*1024,
+    listen = os.getenv("LISTEN"),
+    memtx_min_tuple_size=32,
+    slab_alloc_factor=1.03
+})
diff --git a/test/engine/gh-5216-small_alloc_factor.result b/test/engine/gh-5216-small_alloc_factor.result
+env = require('test_run')
+---
+...
+test_run = env.new()
+---
+...
+test_run:cmd('create server test with script="engine/gh-5216-small_alloc_factor.lua"')
+---
+- true
+...
+test_run:cmd('start server test with args="none"')
+---
+- true
+...
+test_run:cmd('switch test')
+---
+- true
+...
+s = box.schema.space.create('test')
+---
+...
+_ = s:create_index('test')
+---
+...
+function str(i) return string.rep('a', math.floor(256 * math.pow(1.03, i))) end
+---
+...
+for i=1,276 do _ = s:replace{i+200, str(i)} end
+---
+...
+for i=1,274 do _ = s:delete{i+200} end
+---
+...
+collectgarbage('collect')
+---
+- 0
+...
+_ = s:replace{200+277, str(275)}
+---
+...
+_ = s:delete{200+275}
+---
+...
+collectgarbage('collect')
+---
+- 0
+...
+_ = s:delete{200+276}
+---
+...
+collectgarbage('collect')
+---
+- 0
+...
+test_run:cmd('switch default')
+---
+- true
+...
+test_run:cmd('stop server test')
+---
+- true
+...
+test_run:cmd('cleanup server test')
+---
+- true
+...
+test_run:cmd('delete server test')
+---
+- true
+...
diff --git a/test/engine/gh-5216-small_alloc_factor.test.lua b/test/engine/gh-5216-small_alloc_factor.test.lua
+env = require('test_run')
+test_run = env.new()
+test_run:cmd('create server test with script="engine/gh-5216-small_alloc_factor.lua"')
+test_run:cmd('start server test with args="none"')
+test_run:cmd('switch test')
+s = box.schema.space.create('test')
+_ = s:create_index('test')
+function str(i) return string.rep('a', math.floor(256 * math.pow(1.03, i))) end
+for i=1,276 do _ = s:replace{i+200, str(i)} end
+for i=1,274 do _ = s:delete{i+200} end
+collectgarbage('collect')
+_ = s:replace{200+277, str(275)}
+_ = s:delete{200+275}
+collectgarbage('collect')
+_ = s:delete{200+276}
+collectgarbage('collect')
+test_run:cmd('switch default')
+test_run:cmd('stop server test')
+test_run:cmd('cleanup server test')
+test_run:cmd('delete server test')

 
 
 

[-- Attachment #2: Type: text/html, Size: 10932 bytes --]

^ permalink raw reply	[flat|nested] 14+ messages in thread

* Re: [Tarantool-patches] FW:  [PATCH v2 1/3] small: implement new size class evaluation
       [not found]     ` <A90D94B7-298A-4D1B-8134-6EE2ED45D615@hxcore.ol>
@ 2020-12-25  7:48       ` Evgeny Mekhanik
  0 siblings, 0 replies; 14+ messages in thread
From: Evgeny Mekhanik @ 2020-12-25  7:48 UTC (permalink / raw)
  To: Vladislav Shpilevoy; +Cc: tarantool-patches

[-- Attachment #1: Type: text/plain, Size: 2458 bytes --]


 
>> I don't understand. So you can make the factor smaller than it was
>> requested? What is the point in configuring the factor then?
> 9. The user configures the allocation factor, the actual factor may differ,
>    but it depends directly on the parameter set by the user.
>    User can choose the parameter so that it suits the real allocation factor.
 
But this is not the answer on the question, is it? What is the point is
making it bigger if it can get smaller in the result? And the user can't
even understand how to select the factor he actually needs. For instance,
he sets 1.5, but he has no idea what will be the final value. How can one
tune it then? How to choose the value?
 
Answer:
This is an approximating function, so it really changes the allocation factor. 
 We can pass the real factor up and print it so that the user understands the real value 
 
> diff --git a/small/small_class.h b/small/small_class.h
> new file mode 100644
> index 0000000..0677557
> --- /dev/null
> +++ b/small/small_class.h
> @@ -0,0 +1,218 @@
> +
> +/**
> + * CHAR_BIT
> + */
> +#include <limits.h>
> +
> +/**
> + *
 
Unnecessary empty line.
 
Fixed: Delete unnecessary empty line.
+/**
+ * CHAR_BIT
+ */
+#include <limits.h>
+
+/**
+ * small_alloc uses a collection of mempools of different sizes.
 
 
> + * small_alloc uses a collection of mempools of different sizes.
> + * If small_alloc stores all mempools in an array then it have to determine
> + * an offset in that array where the most suitable mempool is.
> + * Let's name the offset as 'size class' and the size that the corresponding
> + * mempool allocates as 'class size'.> diff --git a/test/small_class.c b/test/small_class.c
> new file mode 100644
> index 0000000..b56cfeb
> --- /dev/null
> +++ b/test/small_class.c
> @@ -0,0 +1,176 @@
> +#include "small/small_class.h"
> +#include "unit.h"
> +#include <math.h>
> +
> +#define SZR(arr) sizeof(arr) / sizeof(arr[0])
 
We have lengthof() in trivia/util.h.
 
Answer:
 
We can't use lengthof() from trivia/util.h, because this file is not a part of small project.
 Small should be built by itself without dependencies from third-party components, but
 i change my macro SZR to lengthof as you can see in patch below:
 
+#include "small/small_class.h"
+#include "unit.h"
+#include <math.h>
+
+#ifndef lengthof
+#define lengthof(array) (sizeof (array) / sizeof ((array)[0]))
+#endif
+
+static void
+test_class(void)
 
 
 

[-- Attachment #2: Type: text/html, Size: 5255 bytes --]

^ permalink raw reply	[flat|nested] 14+ messages in thread

* Re: [Tarantool-patches] FW: [PATCH v2 3/3] small: changed small allocator pool management
       [not found]     ` <27E47303-4307-4713-BB8A-2427FED09DDE@hxcore.ol>
@ 2020-12-25  7:52       ` Evgeny Mekhanik
  2020-12-25  7:56       ` Evgeny Mekhanik
  1 sibling, 0 replies; 14+ messages in thread
From: Evgeny Mekhanik @ 2020-12-25  7:52 UTC (permalink / raw)
  To: Vladislav Shpilevoy; +Cc: tarantool-patches

[-- Attachment #1: Type: text/plain, Size: 925 bytes --]


 
On 23.12.2020 14:14, mechanik20051988 wrote:
> 1. Fxed
> 2. As i understand you comment, you wrote that pools
>    should be aligned on the 8-byte boundary.
>    This is guaranteed by the granularity parameter in small_class if min_alloc
>    have 8-byte boundary alignment. We calculate
>    min_alloc = objsize_min = small_align(objsize_min, sizeof(intptr_t));
>    and pass granularity sizeof(uintptr_t).
 
No, I meant the indentation alignment is broken. If a
function call consists of multiple lines, the non-first
lines should be aligned by '(' + 1. See examples in
the existing code.
 
 Change alignment in code, see below:
+    small_class_create(&alloc->small_class, sizeof(intptr_t),
+                                   alloc->factor, objsize_min);
+    factor_pool_create(alloc);
 
     lifo_init(&alloc->delayed);
     lifo_init(&alloc->delayed_large);
 
 

[-- Attachment #2: Type: text/html, Size: 2051 bytes --]

^ permalink raw reply	[flat|nested] 14+ messages in thread

* Re: [Tarantool-patches] FW: [PATCH v2 3/3] small: changed small allocator pool management
       [not found]     ` <27E47303-4307-4713-BB8A-2427FED09DDE@hxcore.ol>
  2020-12-25  7:52       ` [Tarantool-patches] FW: " Evgeny Mekhanik
@ 2020-12-25  7:56       ` Evgeny Mekhanik
  1 sibling, 0 replies; 14+ messages in thread
From: Evgeny Mekhanik @ 2020-12-25  7:56 UTC (permalink / raw)
  To: Vladislav Shpilevoy; +Cc: tarantool-patches

[-- Attachment #1: Type: text/plain, Size: 816 bytes --]


 
 
 
Thanks for the fixes!
 
On 23.12.2020 14:14, mechanik20051988 wrote:
> 1. Fxed
> 2. As i understand you comment, you wrote that pools
>    should be aligned on the 8-byte boundary.
>    This is guaranteed by the granularity parameter in small_class if min_alloc
>    have 8-byte boundary alignment. We calculate
>    min_alloc = objsize_min = small_align(objsize_min, sizeof(intptr_t));
>    and pass granularity sizeof(uintptr_t).
 
No, I meant the indentation alignment is broken. If a
function call consists of multiple lines, the non-first
lines should be aligned by '(' + 1. See examples in
the existing code.
 
Fixed:
+    small_class_create(&alloc->small_class, sizeof(intptr_t),
+               alloc->factor, objsize_min);
+    factor_pool_create(alloc);
 
 
 

[-- Attachment #2: Type: text/html, Size: 2010 bytes --]

^ permalink raw reply	[flat|nested] 14+ messages in thread

* Re: [Tarantool-patches] FW: [PATCH] memtx: change small allocator behavior
  2020-12-25  7:42       ` [Tarantool-patches] FW: " Evgeny Mekhanik
@ 2020-12-28 12:10         ` Vladislav Shpilevoy
  0 siblings, 0 replies; 14+ messages in thread
From: Vladislav Shpilevoy @ 2020-12-28 12:10 UTC (permalink / raw)
  To: Evgeny Mekhanik; +Cc: tarantool-patches

Hi! Thanks for the answers!

Now much better, I understood almost everything. The only
issue seems to be with your editor now. You have extra
empty lines after each non-empty line in your emails. Do
you use a web version of mail client?

It should be all fixed if you switch to a plain-text client.
It won't ruin the cites and won't add any extra lines.

>> +                alloc_factor = 1.001;
> 
>  
> 
> 2. I don't see the factor being rounded up in the original code.
> 
> Why did you add it? And why 1.0 is bad?
> 
>  
> Answer:
>  
> Here is a code which rounded up alloc factor in master branch.
>     /*
>      * Correct the user-supplied alloc_factor to ensure that
>      * it actually produces growing object sizes.
>      */
>     if (alloc->step_pool_objsize_max * alloc_factor <
>         alloc->step_pool_objsize_max + STEP_SIZE) {
>         alloc_factor =
>             (alloc->step_pool_objsize_max + STEP_SIZE + 0.5)/
>             alloc->step_pool_objsize_max;
>     }
>     I use gdb to show it:
>     tarantool> box.cfg{slab_alloc_factor = 1.01}
>     2020-12-24 19:22:33.416 [22602] main/103/interactive C> Tarantool 2.7.0-148-gd5a5754a3
>     2020-12-24 19:22:33.416 [22602] main/103/interactive C> log level 5
>     2020-12-24 19:22:33.416 [22602] main/103/interactive I> mapping 268435456 bytes for memtx tuple arena...
>     Breakpoint 1, small_alloc_create (alloc=0x555555cfe788, cache=0x555555cfe530, objsize_min=272,
>                           alloc_factor=1.00999999) at /home/evgeny/MASTER/tarantool/src/lib/small/small/small.c:135
>     135                     alloc_factor =
>     (gdb) n
>     139             alloc->factor = alloc_factor;
>     (gdb) p alloc_factor
>     $1 = 1.032197
>     (gdb)
>     As you can see if you pass slab_alloc_factor < 1.03 it's changed to 1.03. I try 0.01 factor and get the same value.
>     It's code from master branch, now user can pass >= 1.001 factor. We can't use 1.0, because we need increment to pool size.

Ok, now I see, thanks.

^ permalink raw reply	[flat|nested] 14+ messages in thread

* Re: [Tarantool-patches] [PATCH v2 1/3] small: implement new size class evaluation
  2020-12-24 15:13   ` Vladislav Shpilevoy
       [not found]     ` <A90D94B7-298A-4D1B-8134-6EE2ED45D615@hxcore.ol>
@ 2020-12-28 12:10     ` Vladislav Shpilevoy
  1 sibling, 0 replies; 14+ messages in thread
From: Vladislav Shpilevoy @ 2020-12-28 12:10 UTC (permalink / raw)
  To: mechanik20051988; +Cc: tarantool-patches

On 24.12.2020 18:13, Vladislav Shpilevoy via Tarantool-patches wrote:
> Thanks for the fixes!
> 
>>> Lets omit unnecessary changes. This clearly has nothing to do with
>>> the functional part of the patch.
>> 1. Fixed
> 
> Nope, it is not. The diff hunk is still here.

It is still here. Don't ignore, please.

I took the latest version of your branch, called `git submodule update`,
went to src/lib/small, and the change is here in the first commit.

^ permalink raw reply	[flat|nested] 14+ messages in thread

end of thread, other threads:[~2020-12-28 12:10 UTC | newest]

Thread overview: 14+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2020-12-23 13:14 [Tarantool-patches] [PATCH v2 0/3] change small allocator behavior mechanik20051988
2020-12-23 13:14 ` [Tarantool-patches] [PATCH] memtx: " mechanik20051988
2020-12-24 15:13   ` Vladislav Shpilevoy
     [not found]     ` <0076A088-8CBC-4238-9EEB-0C73EC516098@hxcore.ol>
2020-12-25  7:42       ` [Tarantool-patches] FW: " Evgeny Mekhanik
2020-12-28 12:10         ` Vladislav Shpilevoy
2020-12-23 13:14 ` [Tarantool-patches] [PATCH v2 1/3] small: implement new size class evaluation mechanik20051988
2020-12-24 15:13   ` Vladislav Shpilevoy
     [not found]     ` <A90D94B7-298A-4D1B-8134-6EE2ED45D615@hxcore.ol>
2020-12-25  7:48       ` [Tarantool-patches] FW: " Evgeny Mekhanik
2020-12-28 12:10     ` [Tarantool-patches] " Vladislav Shpilevoy
2020-12-23 13:14 ` [Tarantool-patches] [PATCH v2 2/3] test: add small allocator performance test mechanik20051988
2020-12-23 13:14 ` [Tarantool-patches] [PATCH v2 3/3] small: changed small allocator pool management mechanik20051988
2020-12-24 15:13   ` Vladislav Shpilevoy
     [not found]     ` <27E47303-4307-4713-BB8A-2427FED09DDE@hxcore.ol>
2020-12-25  7:52       ` [Tarantool-patches] FW: " Evgeny Mekhanik
2020-12-25  7:56       ` Evgeny Mekhanik

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox