Welcome! Log In Create A New Profile

Advanced

[PATCH] Replaced loop with __builtin_ctzl for detecting first 0 in bitnamp

Anonymous User
November 27, 2020 01:24PM
# HG changeset patch
# User Noah Goldstein <goldstein.w.n@gmail.com>
# Date 1606497081 18000
# Fri Nov 27 12:11:21 2020 -0500
# Node ID 7ec2fc7b29d6614df28152dd4a895e6139138890
# Parent 90cc7194e993f8d722347e9f46a00f65dffc3935
Replaced loop with __builtin_ctzl for detecting first 0 in bitnamp
No particular pressing reason for this change other than the performance benefit it yields. Converts a loop that could take 63 iterations (and had a branch) to 5 instructions

diff -r 90cc7194e993 -r 7ec2fc7b29d6 src/core/ngx_slab.c
--- a/src/core/ngx_slab.c Fri Nov 27 00:01:20 2020 +0300
+++ b/src/core/ngx_slab.c Fri Nov 27 12:11:21 2020 -0500
@@ -235,36 +235,33 @@

if (bitmap[n] != NGX_SLAB_BUSY) {

- for (m = 1, i = 0; m; m <<= 1, i++) {
- if (bitmap[n] & m) {
- continue;
+ m = ~bitmap[n];
+ i = __builtin_ctzl(m);
+
+ bitmap[n] = ~(m & (m - 1));
+
+ i = (n * 8 * sizeof(uintptr_t) + i) << shift;
+
+ p = (uintptr_t) bitmap + i;
+
+ pool->stats[slot].used++;
+
+ if (bitmap[n] == NGX_SLAB_BUSY) {
+ for (n = n + 1; n < map; n++) {
+ if (bitmap[n] != NGX_SLAB_BUSY) {
+ goto done;
+ }
}

- bitmap[n] |= m;
-
- i = (n * 8 * sizeof(uintptr_t) + i) << shift;
-
- p = (uintptr_t) bitmap + i;
-
- pool->stats[slot].used++;
+ prev = ngx_slab_page_prev(page);
+ prev->next = page->next;
+ page->next->prev = page->prev;

- if (bitmap[n] == NGX_SLAB_BUSY) {
- for (n = n + 1; n < map; n++) {
- if (bitmap[n] != NGX_SLAB_BUSY) {
- goto done;
- }
- }
+ page->next = NULL;
+ page->prev = NGX_SLAB_SMALL;
+ }

- prev = ngx_slab_page_prev(page);
- prev->next = page->next;
- page->next->prev = page->prev;
-
- page->next = NULL;
- page->prev = NGX_SLAB_SMALL;
- }
-
- goto done;
- }
+ goto done;
}
}

_______________________________________________
nginx-devel mailing list
nginx-devel@nginx.org
http://mailman.nginx.org/mailman/listinfo/nginx-devel
Subject Author Views Posted

[PATCH] Replaced loop with __builtin_ctzl for detecting first 0 in bitnamp

Anonymous User 136 November 27, 2020 01:24PM

Re: [PATCH] Replaced loop with __builtin_ctzl for detecting first 0 in bitnamp

Maxim Dounin 52 November 27, 2020 03:18PM



Sorry, you do not have permission to post/reply in this forum.

Online Users

Guests: 76
Record Number of Users: 6 on February 13, 2018
Record Number of Guests: 421 on December 02, 2018
Powered by nginx      Powered by FreeBSD      PHP Powered      Powered by MariaDB      ipv6 ready