benchmark.c File Reference

Standalone benchmark for libfuzzy. More...

#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include "lib.h"

Include dependency graph for benchmark.c:

Go to the source code of this file.

Functions
static double	get_time_ms (void)
	Get current time in milliseconds.
static void	benchmark_basic (const char *pattern, const char *candidate, int iterations, const char *description)
	Basic pattern matching benchmark.
static void	benchmark_mailbox_list (const char *pattern, int iterations)
	Benchmark searching through mailbox list.
static void	benchmark_options (const char *pattern, const char *candidate, int iterations)
	Benchmark with different options.
int	main (int argc, char *argv[])
	Entry point for fuzzy benchmark.

Variables
static const char *	mailbox_paths []
static const int	NUM_MAILBOXES = sizeof(mailbox_paths) / sizeof(mailbox_paths[0])

Detailed Description

Standalone benchmark for libfuzzy.

Authors

• Richard Russon

Copyright

This program is free software: you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, either version 2 of the License, or (at your option) any later version.

This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.

You should have received a copy of the GNU General Public License along with this program. If not, see http://www.gnu.org/licenses/.

Definition in file benchmark.c.

Function Documentation

get_time_ms()

static double get_time_ms ( void )

static

Get current time in milliseconds.

Return values

num	Current time in milliseconds

Definition at line 86 of file benchmark.c.

{
#if defined(_POSIX_TIMERS) && _POSIX_TIMERS > 0
  struct timespec ts;
  clock_gettime(CLOCK_MONOTONIC, &ts);
  return (ts.tv_sec * 1000.0) + (ts.tv_nsec / 1000000.0);
#else
  // Fallback to less accurate clock()
  return (double) clock() / CLOCKS_PER_SEC * 1000.0;
#endif
}

Here is the caller graph for this function:

benchmark_basic()

static void benchmark_basic ( const char * pattern, const char * candidate, int iterations, const char * description )

static

Basic pattern matching benchmark.

Parameters

pattern	Pattern to match
candidate	Candidate string
iterations	Number of iterations
description	Test description

Definition at line 105 of file benchmark.c.

{
  struct FuzzyOptions opts = { 0 };
  struct FuzzyResult result = { 0 };
 
  double start = get_time_ms();
 
  int matches = 0;
  for (int i = 0; i < iterations; i++)
  {
    int score = fuzzy_match(pattern, candidate, FUZZY_ALGO_SUBSEQ, &opts, &result);
    if (score >= 0)
      matches++;
  }
 
  double end = get_time_ms();
  double elapsed = end - start;
  double per_match = elapsed / iterations;
  double throughput = iterations / (elapsed / 1000.0);
 
  printf("%-50s ", description);
  printf("%8.2f ms  ", elapsed);
  printf("%8.3f µs/op  ", per_match * 1000.0);
  printf("%10.0f ops/sec  ", throughput);
  printf("(%d/%d matches)\n", matches, iterations);
}

Here is the call graph for this function:

Here is the caller graph for this function:

benchmark_mailbox_list()

static void benchmark_mailbox_list ( const char * pattern, int iterations )

static

Benchmark searching through mailbox list.

Parameters

pattern	Pattern to search for
iterations	Number of times to search through all mailboxes

Definition at line 138 of file benchmark.c.

{
  struct FuzzyOptions opts = { .smart_case = true };
  struct FuzzyResult result = { 0 };
 
  double start = get_time_ms();
 
  int total_matches = 0;
  for (int i = 0; i < iterations; i++)
  {
    for (int j = 0; j < NUM_MAILBOXES; j++)
    {
      int score = fuzzy_match(pattern, mailbox_paths[j], FUZZY_ALGO_SUBSEQ, &opts, &result);
      if (score >= 0)
        total_matches++;
    }
  }
 
  double end = get_time_ms();
  double elapsed = end - start;
  int total_ops = iterations * NUM_MAILBOXES;
  double per_match = elapsed / total_ops;
  double throughput = total_ops / (elapsed / 1000.0);
 
  printf("%-50s ", "Mailbox list search");
  printf("%8.2f ms  ", elapsed);
  printf("%8.3f µs/op  ", per_match * 1000.0);
  printf("%10.0f ops/sec  ", throughput);
  printf("(%d matches in %d ops)\n", total_matches, total_ops);
}

Here is the call graph for this function:

Here is the caller graph for this function:

benchmark_options()

static void benchmark_options ( const char * pattern, const char * candidate, int iterations )

static

Benchmark with different options.

Parameters

pattern	Pattern to match
candidate	Candidate string
iterations	Number of iterations

Definition at line 175 of file benchmark.c.

{
  struct FuzzyResult result = { 0 };
 
  // Case insensitive
  {
    struct FuzzyOptions opts = { .case_sensitive = false };
    double start = get_time_ms();
 
    for (int i = 0; i < iterations; i++)
      fuzzy_match(pattern, candidate, FUZZY_ALGO_SUBSEQ, &opts, &result);
 
    double elapsed = get_time_ms() - start;
    printf("%-50s %8.2f ms  %8.3f µs/op\n", "  Case-insensitive", elapsed,
           elapsed / iterations * 1000.0);
  }
 
  // Case sensitive
  {
    struct FuzzyOptions opts = { .case_sensitive = true };
    double start = get_time_ms();
 
    for (int i = 0; i < iterations; i++)
      fuzzy_match(pattern, candidate, FUZZY_ALGO_SUBSEQ, &opts, &result);
 
    double elapsed = get_time_ms() - start;
    printf("%-50s %8.2f ms  %8.3f µs/op\n", "  Case-sensitive", elapsed,
           elapsed / iterations * 1000.0);
  }
 
  // Smart case
  {
    struct FuzzyOptions opts = { .smart_case = true };
    double start = get_time_ms();
 
    for (int i = 0; i < iterations; i++)
      fuzzy_match(pattern, candidate, FUZZY_ALGO_SUBSEQ, &opts, &result);
 
    double elapsed = get_time_ms() - start;
    printf("%-50s %8.2f ms  %8.3f µs/op\n", "  Smart case", elapsed,
           elapsed / iterations * 1000.0);
  }
 
  // With prefix preference
  {
    struct FuzzyOptions opts = { .prefer_prefix = true };
    double start = get_time_ms();
 
    for (int i = 0; i < iterations; i++)
      fuzzy_match(pattern, candidate, FUZZY_ALGO_SUBSEQ, &opts, &result);
 
    double elapsed = get_time_ms() - start;
    printf("%-50s %8.2f ms  %8.3f µs/op\n", "  Prefer prefix", elapsed,
           elapsed / iterations * 1000.0);
  }
}

Here is the call graph for this function:

Here is the caller graph for this function:

main()

int main	(	int	argc,
		char *	argv[] )

Entry point for fuzzy benchmark.

Parameters

argc	Number of arguments
argv	Argument vector

Return values

0

Success

Definition at line 238 of file benchmark.c.

{
  int iterations = 100000;
 
  if (argc > 1)
  {
    iterations = atoi(argv[1]);
    if (iterations <= 0)
      iterations = 100000;
  }
 
  if (iterations < 100)
    iterations = 100;
 
  printf("=================================================================\n");
  printf("libfuzzy Benchmark - %d iterations per test\n", iterations);
  printf("=================================================================\n\n");
 
  printf("Test                                                Time        Per Op        Throughput      Results\n");
  printf("------------------------------------------------------------------------------------------------------------------------------\n");
 
  // Short pattern, short candidate
  benchmark_basic("box", "mailbox", iterations, "Short pattern + short candidate");
 
  // Short pattern, medium candidate
  benchmark_basic("mlnd", "mailinglists/neomutt-dev", iterations,
                  "Short pattern + medium candidate");
 
  // Short pattern, long candidate
  benchmark_basic("arch", "Archive/2024/January/Projects/NeoMutt", iterations,
                  "Short pattern + long candidate");
 
  // Medium pattern, long candidate
  benchmark_basic("archjan", "Archive/2024/January/Projects/NeoMutt",
                  iterations, "Medium pattern + long candidate");
 
  // No match
  benchmark_basic("xyz", "mailbox", iterations, "No match");
 
  // Prefix match
  benchmark_basic("mail", "mailbox", iterations, "Prefix match");
 
  // Scattered match
  benchmark_basic("mlnd", "mailing_list_node_database", iterations, "Scattered match");
 
  // Full match
  benchmark_basic("inbox", "inbox", iterations, "Full match");
 
  printf("\n");
 
  // Mailbox list benchmark
  printf("Realistic Scenario - Searching mailbox list (%d mailboxes)\n", NUM_MAILBOXES);
  printf("------------------------------------------------------------------------------------------------------------------------------\n");
  benchmark_mailbox_list("inbox", iterations / 100);
  benchmark_mailbox_list("mlnd", iterations / 100);
  benchmark_mailbox_list("arch", iterations / 100);
  benchmark_mailbox_list("work", iterations / 100);
 
  printf("\n");
 
  // Options comparison
  printf("Options Comparison\n");
  printf("------------------------------------------------------------------------------------------------------------------------------\n");
  benchmark_options("inbox", "INBOX", iterations);
 
  printf("\n");
 
  printf("=================================================================\n");
  printf("Benchmark Complete\n");
  printf("=================================================================\n");
 
  return 0;
}

Here is the call graph for this function:

Variable Documentation

mailbox_paths

const char* mailbox_paths[]

static

Initial value:

= {
  "INBOX",
  "Archive/2023",
  "Archive/2024/January",
  "Archive/2024/February",
  "Sent",
  "Drafts",
  "Trash",
  "mailinglists/neomutt-dev",
  "mailinglists/neomutt-users",
  "mailinglists/linux-kernel",
  "mailinglists/debian-devel",
  "work/projects/libfuzzy",
  "work/projects/neomutt",
  "work/reports/weekly",
  "work/reports/monthly",
  "personal/family",
  "personal/friends",
  "personal/receipts",
  "notifications/github",
  "notifications/gitlab",
  "shopping/amazon",
  "shopping/ebay",
  "travel/bookings",
  "travel/confirmations",
}

Definition at line 53 of file benchmark.c.

                                     {
  "INBOX",
  "Archive/2023",
  "Archive/2024/January",
  "Archive/2024/February",
  "Sent",
  "Drafts",
  "Trash",
  "mailinglists/neomutt-dev",
  "mailinglists/neomutt-users",
  "mailinglists/linux-kernel",
  "mailinglists/debian-devel",
  "work/projects/libfuzzy",
  "work/projects/neomutt",
  "work/reports/weekly",
  "work/reports/monthly",
  "personal/family",
  "personal/friends",
  "personal/receipts",
  "notifications/github",
  "notifications/gitlab",
  "shopping/amazon",
  "shopping/ebay",
  "travel/bookings",
  "travel/confirmations",
};

NUM_MAILBOXES

const int NUM_MAILBOXES = sizeof(mailbox_paths) / sizeof(mailbox_paths[0])

static

Definition at line 80 of file benchmark.c.