From patchwork Tue Jun 15 20:22:08 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Amit Choudhary X-Patchwork-Id: 1492444 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Authentication-Results: ozlabs.org; spf=pass (sender SPF authorized) smtp.mailfrom=sourceware.org (client-ip=8.43.85.97; helo=sourceware.org; envelope-from=libc-alpha-bounces+incoming=patchwork.ozlabs.org@sourceware.org; receiver=) Authentication-Results: ozlabs.org; dkim=pass (1024-bit key; secure) header.d=sourceware.org header.i=@sourceware.org header.a=rsa-sha256 header.s=default header.b=E3QMhFOP; dkim-atps=neutral Received: from sourceware.org (ip-8-43-85-97.sourceware.org [8.43.85.97]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (4096 bits) server-digest SHA256) (No client certificate requested) by ozlabs.org (Postfix) with ESMTPS id 4G4KW42qZTz9sWD for ; Wed, 16 Jun 2021 06:22:40 +1000 (AEST) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 1DB813892466 for ; Tue, 15 Jun 2021 20:22:38 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 1DB813892466 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=sourceware.org; s=default; t=1623788558; bh=JDAYBxe/z09N3JDVUtv8YYhTTH7K8ZYsfi6hCScjRdI=; h=Date:Subject:To:List-Id:List-Unsubscribe:List-Archive:List-Post: List-Help:List-Subscribe:From:Reply-To:From; b=E3QMhFOP9F+iz0kAmJkq2sfivavQPU2JHgRKoyAaFQ9W/gf1tkTeB4+FhIxXQUdIt /Rx1Efdt/Rj+wH+qVv1Zl5YHTaiRVzbj2gya+EXI9KnQS9xOpcAcf0ICkc622lgpqh uW0lShl7KEiOsd2zKDMoT1xh4FzFyS6M8ONGPjus= X-Original-To: libc-alpha@sourceware.org Delivered-To: libc-alpha@sourceware.org Received: from mail-lj1-x242.google.com (mail-lj1-x242.google.com [IPv6:2a00:1450:4864:20::242]) by sourceware.org (Postfix) with ESMTPS id 72D0E3851C29 for ; Tue, 15 Jun 2021 20:22:22 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 72D0E3851C29 Received: by mail-lj1-x242.google.com with SMTP id b37so422530ljr.13 for ; Tue, 15 Jun 2021 13:22:22 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:from:date:message-id:subject:to; bh=JDAYBxe/z09N3JDVUtv8YYhTTH7K8ZYsfi6hCScjRdI=; b=txYON4TT3X8LTlyBBjTEjGaArgj9WGlz/2fykd4XKIZluPqbeQy89Bi6BLfVLxxr8V CHg8lqZn88t40OK9M7zO3rH0oydr5e1M2+y3JsjmbDcUIkBG9EMKGCBCZhgRSSUIXyEc r/mfDmL8wX3oHAPl0wsWckKJIAOYjQwvM8mLMxecCpZpqL+juQXG17GNunqTQ0203/j0 uPwYP+GK42zarV4ZO2Icr2XL3+t17DlwFRPmV59pbUWe7ZHCWcF+47X/EQM8B52c8qPO y16amUGIiGSZjbqqtp0V/8k3bAuetLEW1XJPS3rZAmRLO1CqPAjLpb4XPt43XVwI//yV mabg== X-Gm-Message-State: AOAM5316mT6c/kXmq1gK2rD34eUuaZrcEosOkRN7tXo0x63AGcT1q0Uq 17jtHJgpd1VgLHCL6xkYy1HtksmQrtn+DsmbEQEhtZE8RtNtOQ== X-Google-Smtp-Source: ABdhPJzRm4NYm9Z0JTKtTdvUfSN48hBv1KEzldzRR26fN1hbvcJ3NIM54T59kPk+v20sLONyOUCHCRgDhUB0uMxk22w= X-Received: by 2002:a2e:6e06:: with SMTP id j6mr1248536ljc.3.1623788540614; Tue, 15 Jun 2021 13:22:20 -0700 (PDT) MIME-Version: 1.0 Date: Wed, 16 Jun 2021 01:52:08 +0530 Message-ID: Subject: [Confirmed for long needles] Fastest String Search Algorithm. To: GNU C Library X-Spam-Status: No, score=0.2 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, FREEMAIL_ENVFROM_END_DIGIT, FREEMAIL_FROM, KAM_ASCII_DIVIDERS, RCVD_IN_DNSWL_NONE, SPF_HELO_NONE, SPF_PASS, TXREP autolearn=no autolearn_force=no version=3.4.2 X-Spam-Checker-Version: SpamAssassin 3.4.2 (2018-09-13) on server2.sourceware.org X-BeenThere: libc-alpha@sourceware.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Libc-alpha mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-Patchwork-Original-From: Amit Choudhary via Libc-alpha From: Amit Choudhary Reply-To: Amit Choudhary Errors-To: libc-alpha-bounces+incoming=patchwork.ozlabs.org@sourceware.org Sender: "Libc-alpha" Hi, In case someone is interested, else please ignore (just sending on public domain for other people if they do web search) [Tested on latest glibc - glibc-2.33]. I have done final testing with long needles. I modified bench-strstr.c and included my algorithm in it. Attached are the diff, analysis.xlsx, and original bench-strstr.out. Below is my code: ============================================================================================== // Choudhary algorithm static char * chal(char *text, char *pattern) { #define false 0 #define true 1 #define ALPHABET_SIZE 256 long i = 0; long index = 0; long end_index = 0; int not_found = false; long text_len = strlen(text); long pattern_len = strlen(pattern); long pi_44 = pattern_len - 1; long pi_34 = (3 * pattern_len) / 4; long pi_24 = pattern_len / 2; long pi_14 = pattern_len / 4; long fps = 0; long skip_table[ALPHABET_SIZE] = {0}; // preprocess pattern and fill skip_table for (i = 0; i < pattern_len; i++) { skip_table[(int)(pattern[i])] = pattern_len - 1 - i; } // now search for (i = 0; i < text_len; i++) { if ((text_len - i) < pattern_len) { //printf("\tfps = %ld\n", fps); return NULL; //return -1; } if (pattern[pi_44] != text[i + pi_44]) { if (skip_table[(int)(text[i + pi_44])] > 0) { i = i + skip_table[(int)(text[i + pi_44])] - 1; } continue; } if (pattern[0] != text[i]) { continue; } if (pattern[pi_24] != text[i + pi_24]) { continue; } if (pattern[pi_34] != text[i + pi_34]) { continue; } if (pattern[pi_14] != text[i + pi_14]) { continue; } fps = fps + 1; end_index = i + pi_44; not_found = false; for (index = i; index <= end_index; index++) { if (text[index] != pattern[index - i]) { not_found = true; break; } } // end of inner for loop if (not_found == false) { // match is found //printf("\tfps = %ld\n", fps); return (text + i); //return i; } } // end of outer for loop //printf("\tfps = %ld\n", fps); return NULL; //return -1; } // end of chal ============================================================================================== Amit diff -ru glibc-2.33.orig/benchtests/bench-strstr.c glibc-2.33/benchtests/bench-strstr.c --- glibc-2.33.orig/benchtests/bench-strstr.c 2021-02-01 22:45:33.000000000 +0530 +++ glibc-2.33/benchtests/bench-strstr.c 2021-06-16 01:22:34.320912352 +0530 @@ -45,6 +45,8 @@ "library functions, and _where_ in this manual you can find more specific " "information about them.\n"; +static char *chal(char *text, char *pattern); + /* Simple yet efficient strstr - for needles < 32 bytes it is 2-4 times faster than the optimized twoway_strstr. */ static char * @@ -125,6 +127,7 @@ typedef char *(*proto_t) (const char *, const char *); IMPL (strstr, 1) +IMPL (chal, 0) IMPL (twoway_strstr, 0) IMPL (basic_strstr, 0) @@ -210,6 +213,7 @@ increasing needle sizes. The slowest cases of the two implementations are within a factor of 2 on several different microarchitectures. */ +#if 0 static void test_hard_needle (size_t ne_len, size_t hs_len) { @@ -278,6 +282,94 @@ putchar ('\n'); } } +#endif + +// Choudhary algorithm +static char * +chal(char *text, char *pattern) +{ + +#define false 0 +#define true 1 +#define ALPHABET_SIZE 256 + + long i = 0; + long index = 0; + long end_index = 0; + int not_found = false; + + long text_len = strlen(text); + long pattern_len = strlen(pattern); + + long pi_44 = pattern_len - 1; + long pi_34 = (3 * pattern_len) / 4; + long pi_24 = pattern_len / 2; + long pi_14 = pattern_len / 4; + + long fps = 0; + long skip_table[ALPHABET_SIZE] = {0}; + + // preprocess pattern and fill skip_table + for (i = 0; i < pattern_len; i++) { + skip_table[(int)(pattern[i])] = pattern_len - 1 - i; + } + + // now search + for (i = 0; i < text_len; i++) { + + if ((text_len - i) < pattern_len) { + //printf("\tfps = %ld\n", fps); + return NULL; + //return -1; + } + + if (pattern[pi_44] != text[i + pi_44]) { + if (skip_table[(int)(text[i + pi_44])] > 0) { + i = i + skip_table[(int)(text[i + pi_44])] - 1; + } + continue; + } + + if (pattern[0] != text[i]) { + continue; + } + + if (pattern[pi_24] != text[i + pi_24]) { + continue; + } + + if (pattern[pi_34] != text[i + pi_34]) { + continue; + } + + if (pattern[pi_14] != text[i + pi_14]) { + continue; + } + + fps = fps + 1; + end_index = i + pi_44; + not_found = false; + + for (index = i; index <= end_index; index++) { + if (text[index] != pattern[index - i]) { + not_found = true; + break; + } + } // end of inner for loop + + if (not_found == false) { // match is found + //printf("\tfps = %ld\n", fps); + return (text + i); + //return i; + } + + } // end of outer for loop + + //printf("\tfps = %ld\n", fps); + return NULL; + //return -1; + +} // end of chal static int test_main (void) @@ -292,20 +384,21 @@ for (size_t hlen = 64; hlen <= 256; hlen += 32) for (size_t klen = 1; klen <= 16; klen++) { - do_test (1, 3, hlen, klen, 0); - do_test (0, 9, hlen, klen, 1); + //do_test (1, 3, hlen, klen, 0); + //do_test (0, 9, hlen, klen, 1); } - for (size_t hlen = 256; hlen <= 65536; hlen *= 2) - for (size_t klen = 16; klen <= 256; klen *= 2) + for (size_t hlen = 1024; hlen <= 65536; hlen *= 2) + //for (size_t klen = 16; klen <= 256; klen *= 2) + for (size_t klen = 1024; klen <= hlen; klen *= 2) { do_test (1, 11, hlen, klen, 0); do_test (14, 5, hlen, klen, 1); } - test_hard_needle (64, 65536); - test_hard_needle (256, 65536); - test_hard_needle (1024, 65536); + //test_hard_needle (64, 65536); + //test_hard_needle (256, 65536); + //test_hard_needle (1024, 65536); return ret; }