From 5d67cc7f4c176ea6ab4d2538443d5fe264152861 Mon Sep 17 00:00:00 2001 From: Sverker Eriksson Date: Wed, 19 Jun 2013 18:34:56 +0200 Subject: erts: Add new allocator strategy aoffcbf with better performance than aoffcaobf as we don't have to rearrange the search tree when there are blocks of equal size. --- .../test/alloc_SUITE_data/allocator_test.h | 3 +- erts/emulator/test/alloc_SUITE_data/coalesce.c | 2 +- erts/emulator/test/alloc_SUITE_data/rbtree.c | 90 +++++++++++----------- 3 files changed, 48 insertions(+), 47 deletions(-) (limited to 'erts/emulator/test') diff --git a/erts/emulator/test/alloc_SUITE_data/allocator_test.h b/erts/emulator/test/alloc_SUITE_data/allocator_test.h index c37b074f93..2d6c5f9dc7 100644 --- a/erts/emulator/test/alloc_SUITE_data/allocator_test.h +++ b/erts/emulator/test/alloc_SUITE_data/allocator_test.h @@ -102,7 +102,8 @@ typedef void* erts_cond; #define RBT_IS_TREE(T) ((Ulong) ALC_TEST1(RBT_OP(7), (T))) #define IS_BF_ALGO(A) ((Ulong) ALC_TEST1(RBT_OP(8), (A))) #define RBT_MAX_SZ(T) ((Ulong) ALC_TEST1(RBT_OP(9), (T))) -#define IS_CBF(A) ((Ulong) ALC_TEST1(RBT_OP(0xa), (A))) +#define IS_BF(A) ((Ulong) ALC_TEST1(RBT_OP(0xa), (A))) +#define RBT_PREV(T) ((RBTL_t *) ALC_TEST1(RBT_OP(0xb), (T))) /* From erl_mseg.c */ #define HAVE_MSEG() ((int) ALC_TEST0(0x400)) diff --git a/erts/emulator/test/alloc_SUITE_data/coalesce.c b/erts/emulator/test/alloc_SUITE_data/coalesce.c index 36710bf7b5..9da49a0d14 100644 --- a/erts/emulator/test/alloc_SUITE_data/coalesce.c +++ b/erts/emulator/test/alloc_SUITE_data/coalesce.c @@ -267,7 +267,7 @@ void testcase_run(TestCaseState_t *tcs) { char *argv_org[] = {"-tsmbcs511","-tmmbcs511", "-tsbct512", "-trmbcmt100", "-tas", NULL, NULL}; - char *alg[] = {"af", "gf", "bf", "aobf", "aoff", "aoffcaobf", NULL}; + char *alg[] = {"af", "gf", "bf", "aobf", "aoff", "aoffcbf", "aoffcaobf", NULL}; int i; for (i = 0; alg[i]; i++) { diff --git a/erts/emulator/test/alloc_SUITE_data/rbtree.c b/erts/emulator/test/alloc_SUITE_data/rbtree.c index 702f075304..49df2f0245 100644 --- a/erts/emulator/test/alloc_SUITE_data/rbtree.c +++ b/erts/emulator/test/alloc_SUITE_data/rbtree.c @@ -85,23 +85,21 @@ print_tree(TestCaseState_t *tcs, RBT_t *root) static RBT_t * check_tree(TestCaseState_t *tcs, Allctr_t *alc, Ulong size) { - enum { BF, AOBF, AOFF, AOFFCAOBF }type; + enum { BF, AOBF, AOFF } type; int i, max_i; char stk[128]; RBT_t *root, *x, *y, *res; Ulong x_sz, y_sz, is_x_black; long blacks, curr_blacks; + int have_max_sz; res = NULL; - if (IS_BF_ALGO(alc)) { - if (IS_AOBF(alc)) type = AOBF; - else type = BF; - } - else { /* AOFF_ALGO */ - if (IS_CBF(alc)) type = AOFFCAOBF; - else type = AOFF; - } + if (IS_AOBF(alc)) type = AOBF; + else if (IS_BF(alc)) type = BF; + else type = AOFF; + + have_max_sz = !IS_BF_ALGO(alc); root = RBT_ROOT(alc, size); @@ -191,17 +189,10 @@ check_tree(TestCaseState_t *tcs, Allctr_t *alc, Ulong size) break; case AOFF: ASSERT(tcs, y < x); - ASSERT(tcs, RBT_MAX_SZ(y) <= RBT_MAX_SZ(x)); break; - case AOFFCAOBF: - { - void* x_crr = BLK_TO_MBC(x); - void* y_crr = BLK_TO_MBC(y); - ASSERT(tcs, (y < x && (x_crr != y_crr || x_sz == y_sz)) - || (y_sz < x_sz && x_crr == y_crr)); - ASSERT(tcs, RBT_MAX_SZ(y) <= RBT_MAX_SZ(x)); - break; - } + } + if (have_max_sz) { + ASSERT(tcs, RBT_MAX_SZ(y) <= RBT_MAX_SZ(x)); } } @@ -219,27 +210,22 @@ check_tree(TestCaseState_t *tcs, Allctr_t *alc, Ulong size) break; case AOFF: ASSERT(tcs, y > x); - ASSERT(tcs, RBT_MAX_SZ(y) <= RBT_MAX_SZ(x)); break; - case AOFFCAOBF: - { - void* x_crr = BLK_TO_MBC(x); - void* y_crr = BLK_TO_MBC(y); - ASSERT(tcs, (y > x && (x_crr != y_crr || x_sz == y_sz)) - || (y_sz > x_sz && x_crr == y_crr)); - ASSERT(tcs, RBT_MAX_SZ(y) <= RBT_MAX_SZ(x)); - break; - } + } + if (have_max_sz) { + ASSERT(tcs, RBT_MAX_SZ(y) <= RBT_MAX_SZ(x)); } } if (type == BF) { Ulong l_sz; - RBTL_t *l = RBT_NEXT(x); + RBTL_t *l, *prev=x; for (l = RBT_NEXT(x); l; l = RBT_NEXT(l)) { l_sz = BLK_SZ(l); ASSERT(tcs, l_sz == x_sz); ASSERT(tcs, !RBT_IS_TREE(l)); + ASSERT(tcs, RBT_PREV(l) == prev); + prev = l; } } @@ -262,18 +248,7 @@ check_tree(TestCaseState_t *tcs, Allctr_t *alc, Ulong size) res = x; } break; - case AOFFCAOBF: - if (BLK_TO_MBC(x) != BLK_TO_MBC(res) || x_sz == y_sz) { - if (x < res) { - res = x; - } - } - else if (x_sz < y_sz) { - res = x; - } - break; } - } } @@ -310,7 +285,7 @@ do_check(TestCaseState_t *tcs, Allctr_t *a, Ulong size, int ignore_null) tmp = ALLOC(a, sz - ABLK_HDR_SZ); ASSERT(tcs, tmp); y = UMEM2BLK(tmp); - if (!(IS_BF_ALGO(a) && !IS_AOBF(a))) { + if (!IS_BF(a)) { ASSERT(tcs, x == y); } else { @@ -488,6 +463,7 @@ testcase_run(TestCaseState_t *tcs) char *argv2[] = {"-tasaobf", NULL}; char *argv3[] = {"-tasaoff", NULL}; char *argv4[] = {"-tasaoffcaobf", NULL}; + char *argv5[] = {"-tasaoffcbf", NULL}; Allctr_t *a; rbtree_test_data *td; @@ -511,6 +487,7 @@ testcase_run(TestCaseState_t *tcs) ASSERT(tcs, a); ASSERT(tcs, IS_BF_ALGO(a)); ASSERT(tcs, !IS_AOBF(a)); + ASSERT(tcs, IS_BF(a)); test_it(tcs); @@ -529,6 +506,7 @@ testcase_run(TestCaseState_t *tcs) ASSERT(tcs, a); ASSERT(tcs, IS_BF_ALGO(a)); ASSERT(tcs, IS_AOBF(a)); + ASSERT(tcs, !IS_BF(a)); test_it(tcs); @@ -546,7 +524,8 @@ testcase_run(TestCaseState_t *tcs) ASSERT(tcs, a); ASSERT(tcs, !IS_BF_ALGO(a)); - ASSERT(tcs, !IS_CBF(a)); + ASSERT(tcs, !IS_AOBF(a)); + ASSERT(tcs, !IS_BF(a)); test_it(tcs); test_carrier_migration(tcs); @@ -556,7 +535,7 @@ testcase_run(TestCaseState_t *tcs) testcase_printf(tcs, "Address order first fit test succeeded!\n"); - /* Address order first fit, best fit within carrier */ + /* Address order first fit, aobf within carrier */ testcase_printf(tcs, "Starting test of aoffcaobf...\n"); @@ -565,7 +544,28 @@ testcase_run(TestCaseState_t *tcs) ASSERT(tcs, a); ASSERT(tcs, !IS_BF_ALGO(a)); - ASSERT(tcs, IS_CBF(a)); + ASSERT(tcs, IS_AOBF(a)); + ASSERT(tcs, !IS_BF(a)); + + test_it(tcs); + test_carrier_migration(tcs); + + STOP_ALC(a); + td->allocator = NULL; + + testcase_printf(tcs, "aoffcaobf test succeeded!\n"); + + /* Address order first fit, bf within carrier */ + + testcase_printf(tcs, "Starting test of aoffcbf...\n"); + + current_rbt_type_op_base = AO_FIRSTFIT_OP_BASE; + td->allocator = a = START_ALC("rbtree_aoffcbf_", 0, argv5); + + ASSERT(tcs, a); + ASSERT(tcs, !IS_BF_ALGO(a)); + ASSERT(tcs, !IS_AOBF(a)); + ASSERT(tcs, IS_BF(a)); test_it(tcs); test_carrier_migration(tcs); -- cgit v1.2.3