Commits

trunk
Switch branches/tags
All users
Until Dec 25, 2025
December 2025
Su Mo Tu We Th Fr Sa
30 1 2 3 4 5 6
7 8 9 10 11 12 13
14 15 16 17 18 19 20
21 22 23 24 25 26 27
28 29 30 31 1 2 3
4 5 6 7 8 9 10

Commits on December 18, 2025

  1. Add SIMD-accelerated newline scanning (ARM NEON)
    Use ARM NEON SIMD to scan for newlines 16 bytes at a time instead
    of byte-by-byte. Combined with mmap and Boyer-Moore, fixed string
    search is now 2x faster than grep on ARM64.
    espadonne committed
  2. Add full DFA compilation for O(n) regex matching
    Implement subset construction to compile NFA to DFA for patterns
    without anchors. DFA gives O(n) matching vs NFA's O(nm). On some
    patterns, now 1.8x faster than grep.
    espadonne committed
  3. Add lazy DFA caching for 1.5x regex speedup
    - Cache (state_set_hash, char, case_flag) -> next_states transitions
    - Add FNV-1a hash function for state sets
    - 256-entry direct-mapped cache avoids recomputing transitions
    - BRE: 5.67s -> 3.76s (1.5x faster)
    - ERE: 5.51s -> 3.67s (1.5x faster)
    - Now ~3x slower than grep (was ~5x)
    espadonne committed
  4. Integrate NFA optimizer for 2x regex speedup
    - Use optimized_search instead of nfa_search in regex_api
    - Store optimized_nfa_t alongside raw NFA in regex_t
    - Update compiled_patterns_t to intent(inout) for DFA cache
    - Fix empty pattern optimization (was missing optimize_nfa call)
    
    Benchmarks on 145MB file (2M lines):
    - BRE regex: 11.8s -> 5.67s (2.1x faster)
    - ERE regex: 11.8s -> 5.51s (2.1x faster)
    - Fixed string: 0.24s (unchanged, already optimized)
    espadonne committed
  5. Add NFA optimizer module with bit vector state sets
    - Implement state_set_t with O(1) bit vector operations
    - Extract literal prefixes for Boyer-Moore position skipping
    - Add anchored pattern fast path (^ only tests position 1)
    - Pre-compute start state epsilon closure
    - Add DFA cache infrastructure for future lazy DFA
    espadonne committed
  6. Add memory-mapped I/O and Boyer-Moore search for 36x speedup
    Performance improvements:
    - Add ferp_mmap module for memory-mapped file I/O via POSIX mmap
    - Add ferp_search module with Boyer-Moore-Horspool string search
    - Use mmap for all file reads (falls back to standard I/O for stdin)
    - Use Boyer-Moore for fixed string matching (-F mode)
    - Compile patterns for all modes (including fixed strings)
    
    Results on 134MB file (2M lines):
    - Fixed string (-F): 8.2s → 0.24s (36x faster, matches GNU grep)
    - BRE regex: 55.5s → 11.1s (5x faster, NFA still bottleneck)
    - PCRE (-P): ~0.3s (very fast via libpcre2)
    espadonne committed
  7. Fix directory traversal limits for large directory trees
    - Increase directory queue (MAX_DEPTH) from 100 to 10000
    - Increase file collection buffer from 10K to 100K files
    - Fixes missing files when a single directory contains >100 subdirectories
    espadonne committed
  8. Enable OpenMP parallelization for multi-file searches
    - Add -cpp and -fopenmp flags to release builds
    - Enable parallel do for file processing loop
    - Add critical section for output serialization
    - Make collected_files allocatable (reduce stack usage)
    - All 72 tests pass in debug and release modes
    espadonne committed
  9. Replace SAVE context buffers with dynamic allocation
    - Create context_entry_t type with allocatable text field
    - Replace SAVE arrays with locally allocated before_buffer
    - Allocate context buffer on-demand based on opts%before_context
    - Enables thread-safe file processing (no shared state)
    espadonne committed
  10. Add dynamic line reading with allocatable strings
    - Add initial_line_len constant (8KB) for buffer sizing
    - Implement read_line_dynamic() returning allocatable strings
    - Use 64KB read buffer, return trimmed allocatable result
    - Enables thread-safe line reading (no SAVE variables)
    espadonne committed

Commits on December 17, 2025

  1. Add -NUM context shorthand (e.g., -3 = -C 3)
    GNU grep supports -NUM as a shorthand for -C NUM.
    This is commonly used: `grep -3 pattern` instead of `grep -C 3 pattern`.
    espadonne committed
  2. Add Unicode support, increase line buffer, fix mixed line endings
    - Enable PCRE2_UTF and PCRE2_UCP for full Unicode support
    - Unicode character classes (\p{L}, \p{N}, etc.) now work
    - Unicode case folding for -i flag
    - Increase max_line_len from 8KB to 1MB
    - Strip trailing \r for Windows line endings on Unix
    - Add 4 Unicode tests to test suite (71 total)
    espadonne committed
  3. Add full PCRE support via libpcre2
    Implements -P/--perl-regexp with complete PCRE2 functionality:
    - Lookahead/lookbehind assertions
    - Non-capturing groups (?:...)
    - Named groups (?P<name>...)
    - PCRE character classes (\d, \w, \s, etc.)
    - Word boundaries (\b)
    
    New pcre_api.f90 module provides C bindings to libpcre2-8.
    Makefile now links against libpcre2 via pkg-config.
    espadonne committed
  4. Add output enhancements: -o, context lines, color
    - Fix -o to print only matched portions (multiple per line)
    - Implement context lines (-A, -B, -C) with group separators
    - Add --color=always support with ANSI escape codes
    - Add tests for output options and context lines
    espadonne committed
  5. Integrate regex engine for BRE/ERE support
    - Update Makefile with regex module dependencies and comprehensive tests
    - Update ferp_matcher.f90 to use regex_api for pattern matching
    - Update main.f90 to compile patterns once for efficiency
    - Add 36 tests covering BRE, ERE, POSIX classes, anchors, quantifiers
    espadonne committed
  6. Add Thompson NFA regex engine
    - regex_types.f90: Token, AST, and NFA data structures
    - regex_lexer.f90: BRE/ERE pattern tokenization with POSIX classes
    - regex_parser.f90: Recursive descent parser for AST construction
    - regex_nfa.f90: Thompson construction algorithm
    - regex_engine.f90: NFA simulation with epsilon closure
    - regex_api.f90: Public interface (compile, match, search)
    espadonne committed
  7. espadonne committed
  8. espadonne committed
  9. espadonne committed
  10. espadonne committed
  11. espadonne committed