From mboxrd@z Thu Jan 1 00:00:00 1970 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on inbox.vuxu.org X-Spam-Level: X-Spam-Status: No, score=-3.3 required=5.0 tests=DKIM_SIGNED,DKIM_VALID, MAILING_LIST_MULTI,RCVD_IN_DNSWL_MED autolearn=ham autolearn_force=no version=3.4.4 Received: (qmail 9032 invoked from network); 29 Jan 2023 21:44:01 -0000 Received: from lists.zx2c4.com (165.227.139.114) by inbox.vuxu.org with ESMTPUTF8; 29 Jan 2023 21:44:01 -0000 Received: by lists.zx2c4.com (ZX2C4 Mail Server) with ESMTP id 3ad33360; Sun, 29 Jan 2023 21:43:44 +0000 (UTC) Return-Path: Received: from mail-ej1-x62c.google.com (mail-ej1-x62c.google.com [2a00:1450:4864:20::62c]) by lists.zx2c4.com (ZX2C4 Mail Server) with ESMTPS id aa1b10a2 (TLSv1.3:TLS_AES_256_GCM_SHA384:256:NO) for ; Sun, 29 Jan 2023 21:43:42 +0000 (UTC) Received: by mail-ej1-x62c.google.com with SMTP id me3so26913740ejb.7 for ; Sun, 29 Jan 2023 13:43:42 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=mmayer-net.20210112.gappssmtp.com; s=20210112; h=cc:to:subject:message-id:date:from:in-reply-to:references :mime-version:from:to:cc:subject:date:message-id:reply-to; bh=yP9rz7g1bANCgNkCRjC88IuWBZ9ZqAApireM25Z07yU=; b=kJXGVyijgG25RSEMOSHOVs5bHzkBsJx4nFyavBlQKT3a1rMbEPtRqDLdNRhBmucay5 yg2S1e7oapnToY4XAWzs/QT3O+CNmJ4NVAzjWYLqhcUCKzL94YWoHIGTC9l9SnR+8x1N WgeV8iEuy2l2dOCHWU+fsKG3gMGGmIMaamCLzzrAbQMGvJj9WsWs5Yz0WYOTTcyLGQ41 AbfAG+1Dio0AnYZXxvzl3a3+rbk9Nifozk7P+A+uf2b9CRm4tjfRqAgPi9emYLFzRtZB oirPd7SJ3Sawtt1P/ON4F96UcVs2UlZJ/1ZaZEN6w6Uz/xhBxu36gzcGJsMm9+Nqsd2Z 1Dww== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=cc:to:subject:message-id:date:from:in-reply-to:references :mime-version:x-gm-message-state:from:to:cc:subject:date:message-id :reply-to; bh=yP9rz7g1bANCgNkCRjC88IuWBZ9ZqAApireM25Z07yU=; b=boGmVkO/J17q4dpvmo8kvEv0k9Ef9kUupHOn2DsEV/NooG75wWz0lOVjv+p2UTI4r5 RgajLR8TxFnlybyCau/YNEaIDa/Nv6LDdNdotB0y49vvANvPFal9v6sPeQPOEJcCapgP VuWc9J+gfFV0VLikZUlh+LP58e53y1JUlhGT/qsD51PguMlBSWNwV5GJbdeUNrGkONwY 3BKGsm7Wayq7x+ZQjgTbW0yGvmT/KSVWQzE5HPf1IebXkOl/c/RRaJ3mtTT0oGKFsMr5 8Gz7o9BK+EwNs0e/wKjrvro1aE6xhFCKaZD7IAm1ld7xC//psWBT8b2ToFOq5j3UVFz4 FGSA== X-Gm-Message-State: AO0yUKVgz7XeQW3BcCR2IU/g8wKKcDDngJTenUfbci3DpCdYcmgBH+9J vp3f748V22bby1ZM/npt9MsSOiiRydaHLt8zh17Kp8A91bfYTOV3t0mpjQ== X-Google-Smtp-Source: AK7set/eu4o+kRa9NtH4b1m7f/uWVBcGUeiLYtC4NASLo0xntnIuXMEJrTxmqMR5HsMNdI7ldc+85pB8U9MLaLmiiR0= X-Received: by 2002:a17:907:20a3:b0:885:5d1d:e33d with SMTP id pw3-20020a17090720a300b008855d1de33dmr952157ejb.108.1675028620930; Sun, 29 Jan 2023 13:43:40 -0800 (PST) MIME-Version: 1.0 References: <20230127231543.17977-1-code@mmayer.net> <20230127231543.17977-2-code@mmayer.net> In-Reply-To: From: Markus Mayer Date: Sun, 29 Jan 2023 13:43:29 -0800 Message-ID: Subject: Re: [PATCH 1/1] global: provide memrchr implementation for macOS To: CGIT List Cc: Glenn Strauss Content-Type: text/plain; charset="UTF-8" X-BeenThere: cgit@lists.zx2c4.com X-Mailman-Version: 2.1.30rc1 Precedence: list List-Id: List for cgit developers and users List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: cgit-bounces@lists.zx2c4.com Sender: "CGit" On Fri, 27 Jan 2023 at 17:16, Glenn Strauss wrote: > > Fun! A small exercise for comparison if you like. > Cheers, Glenn > > void * > memrchr(const void *s, int c, size_t n) > { > const unsigned char *cp = (const unsigned char *)s + n; > const unsigned char ch = (unsigned char)c; > while (s != cp) { > if (*(--cp) == ch) > return (void *)cp; > } > return NULL; > } Hi all, As promised, I played around a bit. I ran a few experiments with different memrchr() implementations. Everything I did can be found here: https://github.com/mmayer/cgit/tree/memrchr-compare The test-specific code is in the memrchr_test folder[1] within that repo. The four implementations I tried are: memrchr: the original implementation (from Apple's sudo command) that I submitted as v1 memrchr2: Alejandro's suggestion memrchr3: Glen's suggestion memrchr4: for added fun, musl-libc's implementation[2] I also checked the object and assembly files into the repo, so it's easier to look at them if anybody wants to. They live in the memrchr_test/output folder. Here are the results for ARM and x86, both in assembly/object size and runtime. ARM # Object size of memrchr and memrchr2 is the same -rw-r--r-- 1 mmayer staff 552 29 Jan 09:52 memrchr.o -rw-r--r-- 1 mmayer staff 552 29 Jan 09:52 memrchr2.o -rw-r--r-- 1 mmayer staff 544 29 Jan 09:52 memrchr3.o -rw-r--r-- 1 mmayer staff 544 29 Jan 09:52 memrchr4.o # Assembly source of memrchr2 is larger than memrchr -rw-r--r-- 1 mmayer staff 694 29 Jan 09:52 memrchr2.s -rw-r--r-- 1 mmayer staff 691 29 Jan 09:52 memrchr.s -rw-r--r-- 1 mmayer staff 655 29 Jan 09:52 memrchr3.s -rw-r--r-- 1 mmayer staff 655 29 Jan 09:52 memrchr4.s execution time: 18.61453 seconds execution time: 15.39163 seconds execution time: 13.56957 seconds execution time: 13.55493 seconds x86 -rw-r--r-- 1 mmayer staff 656 29 Jan 10:02 memrchr.o -rw-r--r-- 1 mmayer staff 656 29 Jan 10:02 memrchr2.o -rw-r--r-- 1 mmayer staff 656 29 Jan 10:02 memrchr3.o -rw-r--r-- 1 mmayer staff 648 29 Jan 10:02 memrchr4.o -rw-r--r-- 1 mmayer staff 835 29 Jan 10:02 memrchr.s -rw-r--r-- 1 mmayer staff 835 29 Jan 10:02 memrchr2.s -rw-r--r-- 1 mmayer staff 825 29 Jan 10:02 memrchr3.s -rw-r--r-- 1 mmayer staff 818 29 Jan 10:02 memrchr4.s execution time: 20.29937 seconds execution time: 23.67755 seconds execution time: 12.59514 seconds execution time: 11.38668 seconds As you can see, musl-libc provides the smallest implementation that is also the fastest. This is true for ARM and x86. So, I guess it makes the most sense to pick that (memrchr4.c in my experiments). The code is under a MIT license, which I assume is fine for CGIT. What does everybody think? Regards, -Markus [1] https://github.com/mmayer/cgit/tree/memrchr-compare/memrchr_test [2] https://git.musl-libc.org/cgit/musl/tree/src/string/memrchr.c