From c56c6d36c3060e62925f036ad020da1753e48829 Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?Bj=C3=B6rn-Egil=20Dahlberg?= <egil@erlang.org>
Date: Sat, 9 Apr 2016 00:54:40 +0200
Subject: erts: Optimize '++' operator
This also optimizes the BIF lists:append/2
Use one pass to check for properness and copying LHS list.
If LHS turns out not being a proper list, bail and reset htop.
If we run out of heap, allocate a heap-fragment and calculate
the remaining length as normal, thus checking for properness,
and then continue copying.
Measurements shows this being ~50% faster.
---
erts/emulator/beam/erl_bif_lists.c | 93 +++++++++++++++++++++++++++++++-------
1 file changed, 77 insertions(+), 16 deletions(-)
(limited to 'erts')
diff --git a/erts/emulator/beam/erl_bif_lists.c b/erts/emulator/beam/erl_bif_lists.c
index fe64e76575..647a218851 100644
--- a/erts/emulator/beam/erl_bif_lists.c
+++ b/erts/emulator/beam/erl_bif_lists.c
@@ -40,32 +40,93 @@ static BIF_RETTYPE append(Process* p, Eterm A, Eterm B)
Eterm list;
Eterm copy;
Eterm last;
- size_t need;
- Eterm* hp;
+ Eterm* hp = NULL;
Sint i;
- if ((i = erts_list_length(A)) < 0) {
- BIF_ERROR(p, BADARG);
+ list = A;
+
+ if (is_nil(list)) {
+ BIF_RET(B);
}
- if (i == 0) {
- BIF_RET(B);
- } else if (is_nil(B)) {
- BIF_RET(A);
+
+ if (is_not_list(list)) {
+ BIF_ERROR(p, BADARG);
}
- need = 2*i;
- hp = HAlloc(p, need);
- list = A;
+ /* optimistic append on heap first */
+
+ if ((i = HeapWordsLeft(p) / 2) < 4) {
+ goto list_tail;
+ }
+
+ hp = HEAP_TOP(p);
copy = last = CONS(hp, CAR(list_val(list)), make_list(hp+2));
list = CDR(list_val(list));
- hp += 2;
+ hp += 2;
+ i -= 2; /* don't use the last 2 words (extra i--;) */
+
+ while(i-- && is_list(list)) {
+ Eterm* listp = list_val(list);
+ last = CONS(hp, CAR(listp), make_list(hp+2));
+ list = CDR(listp);
+ hp += 2;
+ }
+
+ /* A is proper and B is NIL return A as-is, don't update HTOP */
+
+ if (is_nil(list) && is_nil(B)) {
+ BIF_RET(A);
+ }
+
+ if (is_nil(list)) {
+ HEAP_TOP(p) = hp;
+ CDR(list_val(last)) = B;
+ BIF_RET(copy);
+ }
+
+list_tail:
+
+ if ((i = erts_list_length(list)) < 0) {
+ BIF_ERROR(p, BADARG);
+ }
+
+ /* remaining list was proper and B is NIL */
+ if (is_nil(B)) {
+ BIF_RET(A);
+ }
+
+ if (hp) {
+ /* Note: fall through case, already written
+ * on the heap.
+ * The last 2 words of the heap is not written yet
+ */
+ Eterm *hp_save = hp;
+ ASSERT(i != 0);
+ HEAP_TOP(p) = hp + 2;
+ if (i == 1) {
+ hp[0] = CAR(list_val(list));
+ hp[1] = B;
+ BIF_RET(copy);
+ }
+ hp = HAlloc(p, 2*(i - 1));
+ last = CONS(hp_save, CAR(list_val(list)), make_list(hp));
+ } else {
+ hp = HAlloc(p, 2*i);
+ copy = last = CONS(hp, CAR(list_val(list)), make_list(hp+2));
+ hp += 2;
+ }
+
+ list = CDR(list_val(list));
i--;
+
+ ASSERT(i > -1);
while(i--) {
- Eterm* listp = list_val(list);
- last = CONS(hp, CAR(listp), make_list(hp+2));
- list = CDR(listp);
- hp += 2;
+ Eterm* listp = list_val(list);
+ last = CONS(hp, CAR(listp), make_list(hp+2));
+ list = CDR(listp);
+ hp += 2;
}
+
CDR(list_val(last)) = B;
BIF_RET(copy);
}
--
cgit v1.2.3