aboutsummaryrefslogtreecommitdiffstats
path: root/erts/emulator/beam
diff options
context:
space:
mode:
authorBjörn-Egil Dahlberg <[email protected]>2016-04-09 00:54:40 +0200
committerBjörn-Egil Dahlberg <[email protected]>2016-04-11 13:41:22 +0200
commitc56c6d36c3060e62925f036ad020da1753e48829 (patch)
tree328063629d28cc113d026dbccfa9142be869f1f8 /erts/emulator/beam
parent9e3d98d67a9fbc62aa54b3035b953eb94486cdf7 (diff)
downloadotp-c56c6d36c3060e62925f036ad020da1753e48829.tar.gz
otp-c56c6d36c3060e62925f036ad020da1753e48829.tar.bz2
otp-c56c6d36c3060e62925f036ad020da1753e48829.zip
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.
Diffstat (limited to 'erts/emulator/beam')
-rw-r--r--erts/emulator/beam/erl_bif_lists.c93
1 files changed, 77 insertions, 16 deletions
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);
}