cp-library
This documentation is automatically generated by online-judge-tools/verification-helper
perf/bool_list.py
- View this file on GitHub
- Last update: 2025-07-11 23:11:42+09:00
Depends on
cp_library/bit/popcnt32_fn.py
- cp_library/ds/array/u32f_fn.py
- cp_library/ds/wavelet/bit_array_cls.py
- cp_library/perf/benchmark.py
Code
#!/usr/bin/env python3
"""
Simple boolean list benchmark using the new declarative framework.
Compares different boolean data structures and operations.
"""
import random
import array
import sys
import os
sys.path.insert(0, os.path.dirname(os.path.dirname(os.path.abspath(__file__))))
from cp_library.perf.benchmark import Benchmark, BenchmarkConfig
# Import optional dependencies
try:
import bitarray
HAS_BITARRAY = True
except ImportError:
HAS_BITARRAY = False
try:
from cp_library.ds.wavelet.bit_array_cls import BitArray
HAS_CUSTOM_BITARRAY = True
except ImportError:
HAS_CUSTOM_BITARRAY = False
# Configure benchmark
config = BenchmarkConfig(
name="bool_list",
sizes=[1000000, 100000, 10000, 1000, 100, 10, 1], # Reverse order to warm up JIT
operations=['construction', 'access', 'count', 'sum', 'flip', 'and', 'or'],
iterations=10,
warmup=2,
output_dir="./output/benchmark_results/bool_list"
)
# Create benchmark instance
benchmark = Benchmark(config)
# Data generator
@benchmark.data_generator("default")
def generate_bool_data(size: int, operation: str):
"""Generate boolean data in various formats"""
# Generate random boolean data
bool_list = [random.random() < 0.5 for _ in range(size)]
int_list = [int(b) for b in bool_list]
# Create different representations
array_b = array.array('b', int_list)
array_B = array.array('B', int_list)
# Pack into bytes (8 bits per byte)
bytes_data = bytearray((size + 7) // 8)
for i, bit in enumerate(bool_list):
if bit:
bytes_data[i // 8] |= 1 << (7 - (i % 8))
bytes_data = bytes(bytes_data)
# Create bitarray if available
bit_array = None
if HAS_BITARRAY:
bit_array = bitarray.bitarray(bool_list)
# Create custom BitArray if available
custom_bitarray = None
if HAS_CUSTOM_BITARRAY:
custom_bitarray = BitArray(int_list)
custom_bitarray.build()
# Pre-generate auxiliary data for binary operations
other_bool = [random.random() < 0.5 for _ in range(size)]
other_int = [int(b) for b in other_bool]
return {
'bool_list': bool_list,
'int_list': int_list,
'array_b': array_b,
'array_B': array_B,
'bytes_data': bytes_data,
'bit_array': bit_array,
'custom_bitarray': custom_bitarray,
'other_bool': other_bool,
'other_int': other_int,
'size': size,
'operation': operation
}
# Construction operations
@benchmark.implementation("list_bool", "construction")
def construction_list_bool(data):
"""Construct list[bool] from raw data"""
# Use the same source data for all implementations
raw_data = data['bool_list']
result = list(raw_data) # Create a copy
# Return consistent checksum based on source data
checksum = 0
for i, b in enumerate(raw_data):
if b:
checksum ^= i
return checksum
@benchmark.implementation("list_int", "construction")
def construction_list_int(data):
"""Construct list[int] from raw data"""
# Use the same source data for all implementations
raw_data = data['bool_list']
int_list = [int(b) for b in raw_data]
# Return consistent checksum based on source data
checksum = 0
for i, b in enumerate(raw_data):
if b:
checksum ^= i
return checksum
@benchmark.implementation("array_b", "construction")
def construction_array_b(data):
"""Construct array.array('b') from raw data"""
# Use the same source data for all implementations
raw_data = data['bool_list']
int_list = [int(b) for b in raw_data]
array_b = array.array('b', int_list)
# Return consistent checksum based on source data
checksum = 0
for i, b in enumerate(raw_data):
if b:
checksum ^= i
return checksum
@benchmark.implementation("array_B", "construction")
def construction_array_B(data):
"""Construct array.array('B') from raw data"""
# Use the same source data for all implementations
raw_data = data['bool_list']
int_list = [int(b) for b in raw_data]
array_B = array.array('B', int_list)
# Return consistent checksum based on source data
checksum = 0
for i, b in enumerate(raw_data):
if b:
checksum ^= i
return checksum
@benchmark.implementation("bytes", "construction")
def construction_bytes(data):
"""Construct bytes from raw data"""
# Use the same source data for all implementations
raw_data = data['bool_list']
size = data['size']
bytes_data = bytearray((size + 7) // 8)
for i, bit in enumerate(raw_data):
if bit:
bytes_data[i // 8] |= 1 << (7 - (i % 8))
bytes_data = bytes(bytes_data)
# Return consistent checksum based on source data
checksum = 0
for i, b in enumerate(raw_data):
if b:
checksum ^= i
return checksum
if HAS_BITARRAY:
@benchmark.implementation("bitarray", "construction")
def construction_bitarray(data):
"""Construct bitarray from raw data"""
# Use the same source data for all implementations
raw_data = data['bool_list']
bit_array = bitarray.bitarray(raw_data)
# Return consistent checksum based on source data
checksum = 0
for i, b in enumerate(raw_data):
if b:
checksum ^= i
return checksum
if HAS_CUSTOM_BITARRAY:
@benchmark.implementation("custom_bitarray", "construction")
def construction_custom_bitarray(data):
"""Construct custom BitArray from raw data"""
# Use the same source data for all implementations
raw_data = data['bool_list']
int_list = [int(b) for b in raw_data]
custom_bitarray = BitArray(int_list)
custom_bitarray.build()
# Return consistent checksum based on source data
checksum = 0
for i, b in enumerate(raw_data):
if b:
checksum ^= i
return checksum
# Access operations
@benchmark.implementation("list_bool", "access")
def access_list_bool(data):
"""Access operation on list[bool]"""
lst = data['bool_list']
total = 0
access_count = min(1000, len(lst))
step = max(1, len(lst) // access_count)
for i in range(0, len(lst), step):
if i < len(lst) and lst[i]:
total += 1
return total
@benchmark.implementation("list_int", "access")
def access_list_int(data):
"""Access operation on list[int]"""
lst = data['int_list']
total = 0
access_count = min(1000, len(lst))
step = max(1, len(lst) // access_count)
for i in range(0, len(lst), step):
if i < len(lst) and lst[i]:
total += 1
return total
@benchmark.implementation("array_b", "access")
def access_array_b(data):
"""Access operation on array.array('b')"""
arr = data['array_b']
total = 0
access_count = min(1000, len(arr))
step = max(1, len(arr) // access_count)
for i in range(0, len(arr), step):
if i < len(arr) and arr[i]:
total += 1
return total
# Count operations
@benchmark.implementation("list_bool", "count")
def count_list_bool(data):
"""Count True values in list[bool]"""
return data['bool_list'].count(True)
@benchmark.implementation("list_int", "count")
def count_list_int(data):
"""Count True values in list[int]"""
return sum(data['int_list'])
@benchmark.implementation("array_b", "count")
def count_array_b(data):
"""Count True values in array.array('b')"""
return sum(data['array_b'])
# Sum operations (same as count for boolean data)
@benchmark.implementation("list_bool", "sum")
def sum_list_bool(data):
"""Sum boolean values in list[bool]"""
return sum(data['bool_list'])
@benchmark.implementation("list_int", "sum")
def sum_list_int(data):
"""Sum boolean values in list[int]"""
return sum(data['int_list'])
@benchmark.implementation("array_b", "sum")
def sum_array_b(data):
"""Sum boolean values in array.array('b')"""
return sum(data['array_b'])
# Flip operations
@benchmark.implementation("list_bool", "flip")
def flip_list_bool(data):
"""Flip all boolean values in list[bool]"""
lst = list(data['bool_list']) # Create copy
checksum = 0
for i in range(len(lst)):
lst[i] = not lst[i]
if lst[i]:
checksum ^= i
return checksum
@benchmark.implementation("list_int", "flip")
def flip_list_int(data):
"""Flip all boolean values in list[int]"""
lst = list(data['int_list']) # Create copy
checksum = 0
for i in range(len(lst)):
lst[i] = 1 - lst[i]
if lst[i]:
checksum ^= i
return checksum
@benchmark.implementation("array_b", "flip")
def flip_array_b(data):
"""Flip all boolean values in array.array('b')"""
arr = array.array('b', data['array_b']) # Create copy
checksum = 0
for i in range(len(arr)):
arr[i] = 1 - arr[i]
if arr[i]:
checksum ^= i
return checksum
@benchmark.implementation("array_B", "flip")
def flip_array_B(data):
"""Flip all boolean values in array.array('B')"""
arr = array.array('B', data['array_B']) # Create copy
checksum = 0
for i in range(len(arr)):
arr[i] = 1 - arr[i]
if arr[i]:
checksum ^= i
return checksum
@benchmark.implementation("bytearray", "flip")
def flip_bytearray(data):
"""Flip all boolean values in bytearray (non-bit-packed)"""
# Use int_list as source for non-bit-packed
int_list = data['int_list']
result = bytearray(int_list) # Create copy
checksum = 0
for i in range(len(result)):
result[i] = 1 - result[i]
if result[i]:
checksum ^= i
return checksum
@benchmark.implementation("bytes", "flip")
def flip_bytes(data):
"""Flip all boolean values in bytes (non-bit-packed)"""
# Use int_list as source for non-bit-packed
int_list = data['int_list']
result = bytearray(int_list) # Convert to mutable
checksum = 0
for i in range(len(result)):
result[i] = 1 - result[i]
if result[i]:
checksum ^= i
result = bytes(result) # Convert back to immutable
return checksum
@benchmark.implementation("bytearray_packed", "flip")
def flip_bytearray_packed(data):
"""Flip all boolean values in bytearray (bit-packed)"""
# Use bit-packed bytes_data
size = data['size']
bytes_data = data['bytes_data']
result = bytearray(bytes_data) # Create copy
checksum = 0
# Flip each bit
for i in range(size):
byte_idx = i // 8
bit_idx = 7 - (i % 8)
# Get current bit
current_bit = (result[byte_idx] >> bit_idx) & 1
# Flip the bit
if current_bit:
result[byte_idx] &= ~(1 << bit_idx) # Clear bit
else:
result[byte_idx] |= (1 << bit_idx) # Set bit
checksum ^= i
return checksum
@benchmark.implementation("bytes_packed", "flip")
def flip_bytes_packed(data):
"""Flip all boolean values in bytes (bit-packed)"""
# Use bit-packed bytes_data
size = data['size']
bytes_data = data['bytes_data']
result = bytearray(bytes_data) # Convert to mutable
checksum = 0
# Flip each bit
for i in range(size):
byte_idx = i // 8
bit_idx = 7 - (i % 8)
# Get current bit
current_bit = (result[byte_idx] >> bit_idx) & 1
# Flip the bit
if current_bit:
result[byte_idx] &= ~(1 << bit_idx) # Clear bit
else:
result[byte_idx] |= (1 << bit_idx) # Set bit
checksum ^= i
result = bytes(result) # Convert back to immutable
return checksum
# AND operations
@benchmark.implementation("list_bool", "and")
def and_list_bool(data):
"""AND operation on list[bool]"""
lst = data['bool_list']
other = data['other_bool']
checksum = 0
for i in range(len(lst)):
if lst[i] and other[i]:
checksum ^= i
return checksum
@benchmark.implementation("list_int", "and")
def and_list_int(data):
"""AND operation on list[int]"""
lst = data['int_list']
other = data['other_int']
checksum = 0
for i in range(len(lst)):
if lst[i] & other[i]:
checksum ^= i
return checksum
@benchmark.implementation("array_b", "and")
def and_array_b(data):
"""AND operation on array.array('b')"""
arr = data['array_b']
other = array.array('b', data['other_int'])
checksum = 0
for i in range(len(arr)):
if arr[i] & other[i]:
checksum ^= i
return checksum
@benchmark.implementation("array_B", "and")
def and_array_B(data):
"""AND operation on array.array('B')"""
arr = data['array_B']
other = array.array('B', data['other_int'])
checksum = 0
for i in range(len(arr)):
if arr[i] & other[i]:
checksum ^= i
return checksum
@benchmark.implementation("bytearray", "and")
def and_bytearray(data):
"""AND operation on bytearray (non-bit-packed)"""
arr = bytearray(data['int_list'])
other = bytearray(data['other_int'])
checksum = 0
for i in range(len(arr)):
if arr[i] & other[i]:
checksum ^= i
return checksum
@benchmark.implementation("bytes", "and")
def and_bytes(data):
"""AND operation on bytes (non-bit-packed)"""
arr = bytes(data['int_list'])
other = bytes(data['other_int'])
checksum = 0
for i in range(len(arr)):
if arr[i] & other[i]:
checksum ^= i
return checksum
@benchmark.implementation("bytearray_packed", "and")
def and_bytearray_packed(data):
"""AND operation on bytearray (bit-packed)"""
size = data['size']
bytes_data = data['bytes_data']
other_bool = data['other_bool']
checksum = 0
# AND each bit
for i in range(size):
byte_idx = i // 8
bit_idx = 7 - (i % 8)
# Get bits from both arrays
bit1 = (bytes_data[byte_idx] >> bit_idx) & 1
bit2 = other_bool[i]
# AND operation
if bit1 and bit2:
checksum ^= i
return checksum
@benchmark.implementation("bytes_packed", "and")
def and_bytes_packed(data):
"""AND operation on bytes (bit-packed)"""
size = data['size']
bytes_data = data['bytes_data']
other_bool = data['other_bool']
checksum = 0
# AND each bit
for i in range(size):
byte_idx = i // 8
bit_idx = 7 - (i % 8)
# Get bits from both arrays
bit1 = (bytes_data[byte_idx] >> bit_idx) & 1
bit2 = other_bool[i]
# AND operation
if bit1 and bit2:
checksum ^= i
return checksum
# OR operations
@benchmark.implementation("list_bool", "or")
def or_list_bool(data):
"""OR operation on list[bool]"""
lst = data['bool_list']
other = data['other_bool']
checksum = 0
for i in range(len(lst)):
if lst[i] or other[i]:
checksum ^= i
return checksum
@benchmark.implementation("list_int", "or")
def or_list_int(data):
"""OR operation on list[int]"""
lst = data['int_list']
other = data['other_int']
checksum = 0
for i in range(len(lst)):
if lst[i] | other[i]:
checksum ^= i
return checksum
@benchmark.implementation("array_b", "or")
def or_array_b(data):
"""OR operation on array.array('b')"""
arr = data['array_b']
other = array.array('b', data['other_int'])
checksum = 0
for i in range(len(arr)):
if arr[i] | other[i]:
checksum ^= i
return checksum
@benchmark.implementation("array_B", "or")
def or_array_B(data):
"""OR operation on array.array('B')"""
arr = data['array_B']
other = array.array('B', data['other_int'])
checksum = 0
for i in range(len(arr)):
if arr[i] | other[i]:
checksum ^= i
return checksum
@benchmark.implementation("bytearray", "or")
def or_bytearray(data):
"""OR operation on bytearray (non-bit-packed)"""
arr = bytearray(data['int_list'])
other = bytearray(data['other_int'])
checksum = 0
for i in range(len(arr)):
if arr[i] | other[i]:
checksum ^= i
return checksum
@benchmark.implementation("bytes", "or")
def or_bytes(data):
"""OR operation on bytes (non-bit-packed)"""
arr = bytes(data['int_list'])
other = bytes(data['other_int'])
checksum = 0
for i in range(len(arr)):
if arr[i] | other[i]:
checksum ^= i
return checksum
@benchmark.implementation("bytearray_packed", "or")
def or_bytearray_packed(data):
"""OR operation on bytearray (bit-packed)"""
size = data['size']
bytes_data = data['bytes_data']
other_bool = data['other_bool']
checksum = 0
# OR each bit
for i in range(size):
byte_idx = i // 8
bit_idx = 7 - (i % 8)
# Get bits from both arrays
bit1 = (bytes_data[byte_idx] >> bit_idx) & 1
bit2 = other_bool[i]
# OR operation
if bit1 or bit2:
checksum ^= i
return checksum
@benchmark.implementation("bytes_packed", "or")
def or_bytes_packed(data):
"""OR operation on bytes (bit-packed)"""
size = data['size']
bytes_data = data['bytes_data']
other_bool = data['other_bool']
checksum = 0
# OR each bit
for i in range(size):
byte_idx = i // 8
bit_idx = 7 - (i % 8)
# Get bits from both arrays
bit1 = (bytes_data[byte_idx] >> bit_idx) & 1
bit2 = other_bool[i]
# OR operation
if bit1 or bit2:
checksum ^= i
return checksum
# Add bitarray implementations if available
if HAS_BITARRAY:
@benchmark.implementation("bitarray", ["access", "count", "sum", "flip", "and", "or"])
def bitarray_operations(data):
"""Operations on bitarray"""
operation = data['operation']
bit_arr = data['bit_array']
if operation == 'access':
total = 0
access_count = min(1000, len(bit_arr))
step = max(1, len(bit_arr) // access_count)
for i in range(0, len(bit_arr), step):
if i < len(bit_arr) and bit_arr[i]:
total += 1
return total
elif operation == 'count':
return bit_arr.count(True)
elif operation == 'sum':
return bit_arr.count(True)
elif operation == 'flip':
result = bitarray.bitarray(bit_arr)
result.invert()
checksum = 0
for i, bit in enumerate(result):
if bit:
checksum ^= i
return checksum
elif operation == 'and':
other = bitarray.bitarray(data['other_bool'])
result = bit_arr & other
checksum = 0
for i, bit in enumerate(result):
if bit:
checksum ^= i
return checksum
elif operation == 'or':
other = bitarray.bitarray(data['other_bool'])
result = bit_arr | other
checksum = 0
for i, bit in enumerate(result):
if bit:
checksum ^= i
return checksum
# Add custom BitArray implementations if available
if HAS_CUSTOM_BITARRAY:
@benchmark.implementation("custom_bitarray", ["access", "count", "sum"])
def custom_bitarray_operations(data):
"""Operations on custom BitArray"""
operation = data['operation']
bit_arr = data['custom_bitarray']
if operation == 'access':
total = 0
access_count = min(1000, len(bit_arr))
step = max(1, len(bit_arr) // access_count)
for i in range(0, len(bit_arr), step):
if i < len(bit_arr) and bit_arr[i]:
total += 1
return total
elif operation in ['count', 'sum']:
return sum(bit_arr[i] for i in range(len(bit_arr)))
# Custom validator for boolean operations
@benchmark.validator("default")
def validate_bool_result(expected, actual):
"""Validate boolean operation results"""
# Convert results to comparable format
if hasattr(expected, 'tolist'): # array.array
expected = expected.tolist()
if hasattr(actual, 'tolist'): # array.array
actual = actual.tolist()
# Handle bitarray
if hasattr(expected, 'to01'): # bitarray
expected = [int(b) for b in expected.to01()]
if hasattr(actual, 'to01'): # bitarray
actual = [int(b) for b in actual.to01()]
# Convert booleans to ints for comparison
if isinstance(expected, list) and len(expected) > 0:
if isinstance(expected[0], bool):
expected = [int(b) for b in expected]
if isinstance(actual, list) and len(actual) > 0:
if isinstance(actual[0], bool):
actual = [int(b) for b in actual]
return expected == actual
if __name__ == "__main__":
# Parse command line args and run appropriate mode
runner = benchmark.parse_args()
runner.run()#!/usr/bin/env python3
"""
Simple boolean list benchmark using the new declarative framework.
Compares different boolean data structures and operations.
"""
import random
import array
import sys
import os
sys.path.insert(0, os.path.dirname(os.path.dirname(os.path.abspath(__file__))))
"""
Declarative benchmark framework with minimal boilerplate.
Features:
- Decorator-based benchmark registration
- Automatic data generation and validation
- Built-in timing with warmup
- Configurable operations and sizes
- JSON results and matplotlib plotting
"""
import time
import json
import statistics
import argparse
from typing import Dict, List, Any, Callable, Union
from dataclasses import dataclass
from pathlib import Path
from collections import defaultdict
@dataclass
class BenchmarkConfig:
"""Configuration for benchmark runs"""
name: str
sizes: List[int] = None
operations: List[str] = None
iterations: int = 10
warmup: int = 2
output_dir: str = "./output/benchmark_results"
save_results: bool = True
plot_results: bool = True
plot_scale: str = "loglog" # Options: "loglog", "linear", "semilogx", "semilogy"
progressive: bool = True # Show results operation by operation across sizes
# Profiling mode
profile_mode: bool = False
profile_size: int = None
profile_operation: str = None
profile_implementation: str = None
def __post_init__(self):
if self.sizes is None:
self.sizes = [100, 1000, 10000, 100000]
if self.operations is None:
self.operations = ['default']
class Benchmark:
"""Declarative benchmark framework using decorators"""
def __init__(self, config: BenchmarkConfig):
self.config = config
self.data_generators = {}
self.implementations = {}
self.validators = {}
self.setups = {}
self.results = []
def profile(self, operation: str = None, size: int = None, implementation: str = None):
"""Create a profiling version of this benchmark"""
profile_config = BenchmarkConfig(
name=f"{self.config.name}_profile",
sizes=self.config.sizes,
operations=self.config.operations,
profile_mode=True,
profile_operation=operation,
profile_size=size,
profile_implementation=implementation,
save_results=False,
plot_results=False
)
profile_benchmark = Benchmark(profile_config)
profile_benchmark.data_generators = self.data_generators
profile_benchmark.implementations = self.implementations
profile_benchmark.validators = self.validators
profile_benchmark.setups = self.setups
return profile_benchmark
def parse_args(self):
"""Parse command line arguments for profiling mode"""
parser = argparse.ArgumentParser(
description=f"Benchmark {self.config.name} with optional profiling mode",
formatter_class=argparse.RawDescriptionHelpFormatter,
epilog="""
Examples:
# Normal benchmark mode
python benchmark.py
# Profile specific operation and implementation
python benchmark.py --profile --operation random_access --implementation grid
# Profile with specific size
python benchmark.py --profile --size 1000000
# Profile all implementations of an operation
python benchmark.py --profile --operation construction
"""
)
parser.add_argument('--profile', action='store_true',
help='Run in profiling mode (minimal overhead for profilers)')
parser.add_argument('--operation', type=str,
help=f'Operation to profile. Options: {", ".join(self.config.operations)}')
parser.add_argument('--size', type=int,
help=f'Size to profile. Options: {", ".join(map(str, self.config.sizes))}')
parser.add_argument('--implementation', type=str,
help='Specific implementation to profile (default: all)')
args = parser.parse_args()
# If profile mode requested, return a profiling benchmark
if args.profile:
return self.profile(
operation=args.operation,
size=args.size,
implementation=args.implementation
)
# Otherwise return self for normal mode
return self
def data_generator(self, name: str = "default"):
"""Decorator to register data generator"""
def decorator(func):
self.data_generators[name] = func
return func
return decorator
def implementation(self, name: str, operations: Union[str, List[str]] = None):
"""Decorator to register implementation"""
if operations is None:
operations = ['default']
elif isinstance(operations, str):
operations = [operations]
def decorator(func):
for op in operations:
if op not in self.implementations:
self.implementations[op] = {}
self.implementations[op][name] = func
return func
return decorator
def validator(self, operation: str = "default"):
"""Decorator to register custom validator"""
def decorator(func):
self.validators[operation] = func
return func
return decorator
def setup(self, name: str, operations: Union[str, List[str]] = None):
"""Decorator to register setup function that runs before timing"""
if operations is None:
operations = ['default']
elif isinstance(operations, str):
operations = [operations]
def decorator(func):
for op in operations:
if op not in self.setups:
self.setups[op] = {}
self.setups[op][name] = func
return func
return decorator
def measure_time(self, func: Callable, data: Any, setup_func: Callable = None) -> tuple[Any, float]:
"""Measure execution time with warmup and optional setup"""
# Warmup runs
for _ in range(self.config.warmup):
try:
if setup_func:
setup_data = setup_func(data)
func(setup_data)
else:
func(data)
except Exception:
# If warmup fails, let the main measurement handle the error
break
# Actual measurement
start = time.perf_counter()
for _ in range(self.config.iterations):
if setup_func:
setup_data = setup_func(data)
result = func(setup_data)
else:
result = func(data)
elapsed_ms = (time.perf_counter() - start) * 1000 / self.config.iterations
return result, elapsed_ms
def validate_result(self, expected: Any, actual: Any, operation: str) -> bool:
"""Validate result using custom validator or default comparison"""
if operation in self.validators:
return self.validators[operation](expected, actual)
return expected == actual
def run(self):
"""Run all benchmarks"""
if self.config.profile_mode:
self._run_profile_mode()
else:
self._run_normal_mode()
def _run_normal_mode(self):
"""Run normal benchmark mode"""
print(f"Running {self.config.name}")
print(f"Sizes: {self.config.sizes}")
print(f"Operations: {self.config.operations}")
print("="*80)
# Always show progressive results: operation by operation across all sizes
for operation in self.config.operations:
for size in self.config.sizes:
self._run_single(operation, size)
# Save and plot results
if self.config.save_results:
self._save_results()
if self.config.plot_results:
self._plot_results()
# Print summary
self._print_summary()
def _run_profile_mode(self):
"""Run profiling mode with minimal overhead for use with vmprof"""
operation = self.config.profile_operation or self.config.operations[0]
size = self.config.profile_size or max(self.config.sizes)
impl_name = self.config.profile_implementation
print(f"PROFILING MODE: {self.config.name}")
print(f"Operation: {operation}, Size: {size}")
if impl_name:
print(f"Implementation: {impl_name}")
print("="*80)
print("Run with vmprof: vmprof --web " + ' '.join(sys.argv))
print("="*80)
# Generate test data
generator = self.data_generators.get(operation, self.data_generators.get('default'))
if not generator:
raise ValueError(f"No data generator for operation: {operation}")
test_data = generator(size, operation)
# Get implementations
impls = self.implementations.get(operation, {})
if not impls:
raise ValueError(f"No implementations for operation: {operation}")
# Filter to specific implementation if requested
if impl_name:
if impl_name not in impls:
raise ValueError(f"Implementation '{impl_name}' not found for operation '{operation}'")
impls = {impl_name: impls[impl_name]}
# Run with minimal overhead - no timing, no validation
for name, func in impls.items():
print(f"\nRunning {name}...")
sys.stdout.flush()
# Setup if needed
setup_func = self.setups.get(operation, {}).get(name)
if setup_func:
data = setup_func(test_data)
else:
data = test_data
# Run the actual function (this is what vmprof will profile)
result = func(data)
print(f"Completed {name}, result checksum: {result}")
sys.stdout.flush()
def _run_single(self, operation: str, size: int):
"""Run a single operation/size combination"""
print(f"\nOperation: {operation}, Size: {size}")
print("-" * 50)
sys.stdout.flush()
# Generate test data
generator = self.data_generators.get(operation,
self.data_generators.get('default'))
if not generator:
raise ValueError(f"No data generator for operation: {operation}")
test_data = generator(size, operation)
# Get implementations for this operation
impls = self.implementations.get(operation, {})
if not impls:
print(f"No implementations for operation: {operation}")
return
# Get setup functions for this operation
setups = self.setups.get(operation, {})
# Run reference implementation first
ref_name, ref_impl = next(iter(impls.items()))
ref_setup = setups.get(ref_name)
expected_result, _ = self.measure_time(ref_impl, test_data, ref_setup)
# Run all implementations
for impl_name, impl_func in impls.items():
try:
setup_func = setups.get(impl_name)
result, time_ms = self.measure_time(impl_func, test_data, setup_func)
correct = self.validate_result(expected_result, result, operation)
# Store result
self.results.append({
'operation': operation,
'size': size,
'implementation': impl_name,
'time_ms': time_ms,
'correct': correct,
'error': None
})
status = "OK" if correct else "FAIL"
print(f" {impl_name:<20} {time_ms:>8.3f} ms {status}")
sys.stdout.flush()
except Exception as e:
self.results.append({
'operation': operation,
'size': size,
'implementation': impl_name,
'time_ms': float('inf'),
'correct': False,
'error': str(e)
})
print(f" {impl_name:<20} ERROR: {str(e)[:40]}")
sys.stdout.flush()
def _save_results(self):
"""Save results to JSON"""
output_dir = Path(self.config.output_dir)
output_dir.mkdir(parents=True, exist_ok=True)
filename = output_dir / f"{self.config.name}_{int(time.time())}.json"
with open(filename, 'w') as f:
json.dump(self.results, f, indent=2)
print(f"\nResults saved to {filename}")
def _plot_results(self):
"""Generate plots using matplotlib if available"""
try:
import matplotlib.pyplot as plt
output_dir = Path(self.config.output_dir)
output_dir.mkdir(parents=True, exist_ok=True)
# Group and prepare data for plotting
data_by_op = self._group_results_by_operation()
# Create plots for each operation
for operation, operation_data in data_by_op.items():
self._create_performance_plot(plt, operation, operation_data, output_dir)
except ImportError:
print("Matplotlib not available - skipping plots")
except Exception as e:
print(f"Plotting failed: {e}")
def _group_results_by_operation(self) -> Dict[str, Dict[int, List[Dict[str, Any]]]]:
"""Group results by operation and size for plotting"""
data_by_op = defaultdict(lambda: defaultdict(list))
for r in self.results:
if r['time_ms'] != float('inf') and r['correct']:
data_by_op[r['operation']][r['size']].append({
'implementation': r['implementation'],
'time_ms': r['time_ms']
})
return data_by_op
def _create_performance_plot(self, plt, operation: str, operation_data: Dict[int, List[Dict[str, Any]]], output_dir: Path):
"""Create a performance plot for a single operation"""
sizes = sorted(operation_data.keys())
implementations = set()
for size_data in operation_data.values():
for entry in size_data:
implementations.add(entry['implementation'])
implementations = sorted(implementations)
plt.figure(figsize=(10, 6))
for impl in implementations:
impl_times = []
impl_sizes = []
for size in sizes:
times = [entry['time_ms'] for entry in operation_data[size]
if entry['implementation'] == impl]
if times:
impl_times.append(statistics.mean(times))
impl_sizes.append(size)
if impl_times:
plt.plot(impl_sizes, impl_times, 'o-', label=impl)
plt.xlabel('Input Size')
plt.ylabel('Time (ms)')
plt.title(f'{self.config.name} - {operation} Operation')
plt.legend()
plt.grid(True, alpha=0.3)
# Apply the configured scaling
if self.config.plot_scale == "loglog":
plt.loglog()
elif self.config.plot_scale == "linear":
pass # Default linear scale
elif self.config.plot_scale == "semilogx":
plt.semilogx()
elif self.config.plot_scale == "semilogy":
plt.semilogy()
else:
# Default to loglog if invalid option
plt.loglog()
plot_file = output_dir / f"{self.config.name}_{operation}_performance.png"
plt.savefig(plot_file, dpi=300, bbox_inches='tight')
plt.close()
print(f"Plot saved: {plot_file}")
def _print_summary(self):
"""Print performance summary"""
print("\n" + "="*80)
print("PERFORMANCE SUMMARY")
print("="*80)
# Group by operation
by_operation = defaultdict(lambda: defaultdict(list))
for r in self.results:
if r['error'] is None and r['time_ms'] != float('inf'):
by_operation[r['operation']][r['implementation']].append(r['time_ms'])
print(f"{'Operation':<15} {'Best Implementation':<20} {'Avg Time (ms)':<15} {'Speedup':<10}")
print("-" * 70)
for op, impl_times in sorted(by_operation.items()):
# Calculate averages
avg_times = [(impl, statistics.mean(times))
for impl, times in impl_times.items()]
avg_times.sort(key=lambda x: x[1])
if avg_times:
best_impl, best_time = avg_times[0]
worst_time = avg_times[-1][1]
speedup = worst_time / best_time if best_time > 0 else 0
print(f"{op:<15} {best_impl:<20} {best_time:<15.3f} {speedup:<10.1f}x")
# Import optional dependencies
try:
import bitarray
HAS_BITARRAY = True
except ImportError:
HAS_BITARRAY = False
try:
'''
╺━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━╸
https://kobejean.github.io/cp-library
'''
'''
╺━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━╸
https://kobejean.github.io/cp-library
'''
'''
╺━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━╸
https://kobejean.github.io/cp-library
'''
class BitArray:
def __init__(B, N):
if isinstance(N, list):
# If N is a list, assume it's a list of 1s and 0s
B.N = len(N)
B.Z = (B.N+31)>>5
B.bits, B.cnt = u32f(B.Z+1), u32f(B.Z+1)
# Set bits based on list values
for i, bit in enumerate(N):
if bit: B.set1(i)
elif isinstance(N, (bytes, bytearray)):
# If N is bytes, convert each byte to 8 bits
B.N = len(N) * 8
B.Z = (B.N+31)>>5
B.bits, B.cnt = u32f(B.Z+1), u32f(B.Z+1)
# Set bits based on byte values (MSB first for each byte)
for byte_idx, byte_val in enumerate(N):
for bit_idx in range(8):
if byte_val & (1 << (7 - bit_idx)): # MSB first
B.set1(byte_idx * 8 + bit_idx)
else:
# Original behavior: N is an integer
B.N = N
B.Z = (N+31)>>5
B.bits, B.cnt = u32f(B.Z+1), u32f(B.Z+1)
def build(B):
B.bits.pop()
for i,b in enumerate(B.bits): B.cnt[i+1] = B.cnt[i]+popcnt32(b)
B.bits.append(1)
def __len__(B): return B.N
def __getitem__(B, i: int): return B.bits[i>>5]>>(31-(i&31))&1
def set0(B, i: int): B.bits[i>>5]&=~(1<<31-(i&31))
def set1(B, i: int): B.bits[i>>5]|=1<<31-(i&31)
def count0(B, r: int): return r-B.count1(r)
def count1(B, r: int): return B.cnt[r>>5]+popcnt32(B.bits[r>>5]>>32-(r&31))
def select0(B, k: int):
if not 0<=k<B.N-B.cnt[-1]: return -1
l,r,k=0,B.N,k+1
while 1<r-l:
if B.count0(m:=(l+r)>>1)<k:l=m
else:r=m
return l
def select1(B, k: int):
if not 0<=k<B.cnt[-1]: return -1
l,r,k=0,B.N,k+1
while 1<r-l:
if B.count1(m:=(l+r)>>1)<k:l=m
else:r=m
return l
'''
╺━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━╸
https://kobejean.github.io/cp-library
'''
def popcnt32(x):
x = ((x >> 1) & 0x55555555) + (x & 0x55555555)
x = ((x >> 2) & 0x33333333) + (x & 0x33333333)
x = ((x >> 4) & 0x0f0f0f0f) + (x & 0x0f0f0f0f)
x = ((x >> 8) & 0x00ff00ff) + (x & 0x00ff00ff)
x = ((x >> 16) & 0x0000ffff) + (x & 0x0000ffff)
return x
if hasattr(int, 'bit_count'):
popcnt32 = int.bit_count
'''
╺━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━╸
https://kobejean.github.io/cp-library
'''
'''
╺━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━╸
https://kobejean.github.io/cp-library
'''
'''
╺━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━╸
https://kobejean.github.io/cp-library
'''
from array import array
def u32f(N: int, elm: int = 0): return array('I', (elm,))*N # unsigned int
HAS_CUSTOM_BITARRAY = True
except ImportError:
HAS_CUSTOM_BITARRAY = False
# Configure benchmark
config = BenchmarkConfig(
name="bool_list",
sizes=[1000000, 100000, 10000, 1000, 100, 10, 1], # Reverse order to warm up JIT
operations=['construction', 'access', 'count', 'sum', 'flip', 'and', 'or'],
iterations=10,
warmup=2,
output_dir="./output/benchmark_results/bool_list"
)
# Create benchmark instance
benchmark = Benchmark(config)
# Data generator
@benchmark.data_generator("default")
def generate_bool_data(size: int, operation: str):
"""Generate boolean data in various formats"""
# Generate random boolean data
bool_list = [random.random() < 0.5 for _ in range(size)]
int_list = [int(b) for b in bool_list]
# Create different representations
array_b = array.array('b', int_list)
array_B = array.array('B', int_list)
# Pack into bytes (8 bits per byte)
bytes_data = bytearray((size + 7) // 8)
for i, bit in enumerate(bool_list):
if bit:
bytes_data[i // 8] |= 1 << (7 - (i % 8))
bytes_data = bytes(bytes_data)
# Create bitarray if available
bit_array = None
if HAS_BITARRAY:
bit_array = bitarray.bitarray(bool_list)
# Create custom BitArray if available
custom_bitarray = None
if HAS_CUSTOM_BITARRAY:
custom_bitarray = BitArray(int_list)
custom_bitarray.build()
# Pre-generate auxiliary data for binary operations
other_bool = [random.random() < 0.5 for _ in range(size)]
other_int = [int(b) for b in other_bool]
return {
'bool_list': bool_list,
'int_list': int_list,
'array_b': array_b,
'array_B': array_B,
'bytes_data': bytes_data,
'bit_array': bit_array,
'custom_bitarray': custom_bitarray,
'other_bool': other_bool,
'other_int': other_int,
'size': size,
'operation': operation
}
# Construction operations
@benchmark.implementation("list_bool", "construction")
def construction_list_bool(data):
"""Construct list[bool] from raw data"""
# Use the same source data for all implementations
raw_data = data['bool_list']
result = list(raw_data) # Create a copy
# Return consistent checksum based on source data
checksum = 0
for i, b in enumerate(raw_data):
if b:
checksum ^= i
return checksum
@benchmark.implementation("list_int", "construction")
def construction_list_int(data):
"""Construct list[int] from raw data"""
# Use the same source data for all implementations
raw_data = data['bool_list']
int_list = [int(b) for b in raw_data]
# Return consistent checksum based on source data
checksum = 0
for i, b in enumerate(raw_data):
if b:
checksum ^= i
return checksum
@benchmark.implementation("array_b", "construction")
def construction_array_b(data):
"""Construct array.array('b') from raw data"""
# Use the same source data for all implementations
raw_data = data['bool_list']
int_list = [int(b) for b in raw_data]
array_b = array.array('b', int_list)
# Return consistent checksum based on source data
checksum = 0
for i, b in enumerate(raw_data):
if b:
checksum ^= i
return checksum
@benchmark.implementation("array_B", "construction")
def construction_array_B(data):
"""Construct array.array('B') from raw data"""
# Use the same source data for all implementations
raw_data = data['bool_list']
int_list = [int(b) for b in raw_data]
array_B = array.array('B', int_list)
# Return consistent checksum based on source data
checksum = 0
for i, b in enumerate(raw_data):
if b:
checksum ^= i
return checksum
@benchmark.implementation("bytes", "construction")
def construction_bytes(data):
"""Construct bytes from raw data"""
# Use the same source data for all implementations
raw_data = data['bool_list']
size = data['size']
bytes_data = bytearray((size + 7) // 8)
for i, bit in enumerate(raw_data):
if bit:
bytes_data[i // 8] |= 1 << (7 - (i % 8))
bytes_data = bytes(bytes_data)
# Return consistent checksum based on source data
checksum = 0
for i, b in enumerate(raw_data):
if b:
checksum ^= i
return checksum
if HAS_BITARRAY:
@benchmark.implementation("bitarray", "construction")
def construction_bitarray(data):
"""Construct bitarray from raw data"""
# Use the same source data for all implementations
raw_data = data['bool_list']
bit_array = bitarray.bitarray(raw_data)
# Return consistent checksum based on source data
checksum = 0
for i, b in enumerate(raw_data):
if b:
checksum ^= i
return checksum
if HAS_CUSTOM_BITARRAY:
@benchmark.implementation("custom_bitarray", "construction")
def construction_custom_bitarray(data):
"""Construct custom BitArray from raw data"""
# Use the same source data for all implementations
raw_data = data['bool_list']
int_list = [int(b) for b in raw_data]
custom_bitarray = BitArray(int_list)
custom_bitarray.build()
# Return consistent checksum based on source data
checksum = 0
for i, b in enumerate(raw_data):
if b:
checksum ^= i
return checksum
# Access operations
@benchmark.implementation("list_bool", "access")
def access_list_bool(data):
"""Access operation on list[bool]"""
lst = data['bool_list']
total = 0
access_count = min(1000, len(lst))
step = max(1, len(lst) // access_count)
for i in range(0, len(lst), step):
if i < len(lst) and lst[i]:
total += 1
return total
@benchmark.implementation("list_int", "access")
def access_list_int(data):
"""Access operation on list[int]"""
lst = data['int_list']
total = 0
access_count = min(1000, len(lst))
step = max(1, len(lst) // access_count)
for i in range(0, len(lst), step):
if i < len(lst) and lst[i]:
total += 1
return total
@benchmark.implementation("array_b", "access")
def access_array_b(data):
"""Access operation on array.array('b')"""
arr = data['array_b']
total = 0
access_count = min(1000, len(arr))
step = max(1, len(arr) // access_count)
for i in range(0, len(arr), step):
if i < len(arr) and arr[i]:
total += 1
return total
# Count operations
@benchmark.implementation("list_bool", "count")
def count_list_bool(data):
"""Count True values in list[bool]"""
return data['bool_list'].count(True)
@benchmark.implementation("list_int", "count")
def count_list_int(data):
"""Count True values in list[int]"""
return sum(data['int_list'])
@benchmark.implementation("array_b", "count")
def count_array_b(data):
"""Count True values in array.array('b')"""
return sum(data['array_b'])
# Sum operations (same as count for boolean data)
@benchmark.implementation("list_bool", "sum")
def sum_list_bool(data):
"""Sum boolean values in list[bool]"""
return sum(data['bool_list'])
@benchmark.implementation("list_int", "sum")
def sum_list_int(data):
"""Sum boolean values in list[int]"""
return sum(data['int_list'])
@benchmark.implementation("array_b", "sum")
def sum_array_b(data):
"""Sum boolean values in array.array('b')"""
return sum(data['array_b'])
# Flip operations
@benchmark.implementation("list_bool", "flip")
def flip_list_bool(data):
"""Flip all boolean values in list[bool]"""
lst = list(data['bool_list']) # Create copy
checksum = 0
for i in range(len(lst)):
lst[i] = not lst[i]
if lst[i]:
checksum ^= i
return checksum
@benchmark.implementation("list_int", "flip")
def flip_list_int(data):
"""Flip all boolean values in list[int]"""
lst = list(data['int_list']) # Create copy
checksum = 0
for i in range(len(lst)):
lst[i] = 1 - lst[i]
if lst[i]:
checksum ^= i
return checksum
@benchmark.implementation("array_b", "flip")
def flip_array_b(data):
"""Flip all boolean values in array.array('b')"""
arr = array.array('b', data['array_b']) # Create copy
checksum = 0
for i in range(len(arr)):
arr[i] = 1 - arr[i]
if arr[i]:
checksum ^= i
return checksum
@benchmark.implementation("array_B", "flip")
def flip_array_B(data):
"""Flip all boolean values in array.array('B')"""
arr = array.array('B', data['array_B']) # Create copy
checksum = 0
for i in range(len(arr)):
arr[i] = 1 - arr[i]
if arr[i]:
checksum ^= i
return checksum
@benchmark.implementation("bytearray", "flip")
def flip_bytearray(data):
"""Flip all boolean values in bytearray (non-bit-packed)"""
# Use int_list as source for non-bit-packed
int_list = data['int_list']
result = bytearray(int_list) # Create copy
checksum = 0
for i in range(len(result)):
result[i] = 1 - result[i]
if result[i]:
checksum ^= i
return checksum
@benchmark.implementation("bytes", "flip")
def flip_bytes(data):
"""Flip all boolean values in bytes (non-bit-packed)"""
# Use int_list as source for non-bit-packed
int_list = data['int_list']
result = bytearray(int_list) # Convert to mutable
checksum = 0
for i in range(len(result)):
result[i] = 1 - result[i]
if result[i]:
checksum ^= i
result = bytes(result) # Convert back to immutable
return checksum
@benchmark.implementation("bytearray_packed", "flip")
def flip_bytearray_packed(data):
"""Flip all boolean values in bytearray (bit-packed)"""
# Use bit-packed bytes_data
size = data['size']
bytes_data = data['bytes_data']
result = bytearray(bytes_data) # Create copy
checksum = 0
# Flip each bit
for i in range(size):
byte_idx = i // 8
bit_idx = 7 - (i % 8)
# Get current bit
current_bit = (result[byte_idx] >> bit_idx) & 1
# Flip the bit
if current_bit:
result[byte_idx] &= ~(1 << bit_idx) # Clear bit
else:
result[byte_idx] |= (1 << bit_idx) # Set bit
checksum ^= i
return checksum
@benchmark.implementation("bytes_packed", "flip")
def flip_bytes_packed(data):
"""Flip all boolean values in bytes (bit-packed)"""
# Use bit-packed bytes_data
size = data['size']
bytes_data = data['bytes_data']
result = bytearray(bytes_data) # Convert to mutable
checksum = 0
# Flip each bit
for i in range(size):
byte_idx = i // 8
bit_idx = 7 - (i % 8)
# Get current bit
current_bit = (result[byte_idx] >> bit_idx) & 1
# Flip the bit
if current_bit:
result[byte_idx] &= ~(1 << bit_idx) # Clear bit
else:
result[byte_idx] |= (1 << bit_idx) # Set bit
checksum ^= i
result = bytes(result) # Convert back to immutable
return checksum
# AND operations
@benchmark.implementation("list_bool", "and")
def and_list_bool(data):
"""AND operation on list[bool]"""
lst = data['bool_list']
other = data['other_bool']
checksum = 0
for i in range(len(lst)):
if lst[i] and other[i]:
checksum ^= i
return checksum
@benchmark.implementation("list_int", "and")
def and_list_int(data):
"""AND operation on list[int]"""
lst = data['int_list']
other = data['other_int']
checksum = 0
for i in range(len(lst)):
if lst[i] & other[i]:
checksum ^= i
return checksum
@benchmark.implementation("array_b", "and")
def and_array_b(data):
"""AND operation on array.array('b')"""
arr = data['array_b']
other = array.array('b', data['other_int'])
checksum = 0
for i in range(len(arr)):
if arr[i] & other[i]:
checksum ^= i
return checksum
@benchmark.implementation("array_B", "and")
def and_array_B(data):
"""AND operation on array.array('B')"""
arr = data['array_B']
other = array.array('B', data['other_int'])
checksum = 0
for i in range(len(arr)):
if arr[i] & other[i]:
checksum ^= i
return checksum
@benchmark.implementation("bytearray", "and")
def and_bytearray(data):
"""AND operation on bytearray (non-bit-packed)"""
arr = bytearray(data['int_list'])
other = bytearray(data['other_int'])
checksum = 0
for i in range(len(arr)):
if arr[i] & other[i]:
checksum ^= i
return checksum
@benchmark.implementation("bytes", "and")
def and_bytes(data):
"""AND operation on bytes (non-bit-packed)"""
arr = bytes(data['int_list'])
other = bytes(data['other_int'])
checksum = 0
for i in range(len(arr)):
if arr[i] & other[i]:
checksum ^= i
return checksum
@benchmark.implementation("bytearray_packed", "and")
def and_bytearray_packed(data):
"""AND operation on bytearray (bit-packed)"""
size = data['size']
bytes_data = data['bytes_data']
other_bool = data['other_bool']
checksum = 0
# AND each bit
for i in range(size):
byte_idx = i // 8
bit_idx = 7 - (i % 8)
# Get bits from both arrays
bit1 = (bytes_data[byte_idx] >> bit_idx) & 1
bit2 = other_bool[i]
# AND operation
if bit1 and bit2:
checksum ^= i
return checksum
@benchmark.implementation("bytes_packed", "and")
def and_bytes_packed(data):
"""AND operation on bytes (bit-packed)"""
size = data['size']
bytes_data = data['bytes_data']
other_bool = data['other_bool']
checksum = 0
# AND each bit
for i in range(size):
byte_idx = i // 8
bit_idx = 7 - (i % 8)
# Get bits from both arrays
bit1 = (bytes_data[byte_idx] >> bit_idx) & 1
bit2 = other_bool[i]
# AND operation
if bit1 and bit2:
checksum ^= i
return checksum
# OR operations
@benchmark.implementation("list_bool", "or")
def or_list_bool(data):
"""OR operation on list[bool]"""
lst = data['bool_list']
other = data['other_bool']
checksum = 0
for i in range(len(lst)):
if lst[i] or other[i]:
checksum ^= i
return checksum
@benchmark.implementation("list_int", "or")
def or_list_int(data):
"""OR operation on list[int]"""
lst = data['int_list']
other = data['other_int']
checksum = 0
for i in range(len(lst)):
if lst[i] | other[i]:
checksum ^= i
return checksum
@benchmark.implementation("array_b", "or")
def or_array_b(data):
"""OR operation on array.array('b')"""
arr = data['array_b']
other = array.array('b', data['other_int'])
checksum = 0
for i in range(len(arr)):
if arr[i] | other[i]:
checksum ^= i
return checksum
@benchmark.implementation("array_B", "or")
def or_array_B(data):
"""OR operation on array.array('B')"""
arr = data['array_B']
other = array.array('B', data['other_int'])
checksum = 0
for i in range(len(arr)):
if arr[i] | other[i]:
checksum ^= i
return checksum
@benchmark.implementation("bytearray", "or")
def or_bytearray(data):
"""OR operation on bytearray (non-bit-packed)"""
arr = bytearray(data['int_list'])
other = bytearray(data['other_int'])
checksum = 0
for i in range(len(arr)):
if arr[i] | other[i]:
checksum ^= i
return checksum
@benchmark.implementation("bytes", "or")
def or_bytes(data):
"""OR operation on bytes (non-bit-packed)"""
arr = bytes(data['int_list'])
other = bytes(data['other_int'])
checksum = 0
for i in range(len(arr)):
if arr[i] | other[i]:
checksum ^= i
return checksum
@benchmark.implementation("bytearray_packed", "or")
def or_bytearray_packed(data):
"""OR operation on bytearray (bit-packed)"""
size = data['size']
bytes_data = data['bytes_data']
other_bool = data['other_bool']
checksum = 0
# OR each bit
for i in range(size):
byte_idx = i // 8
bit_idx = 7 - (i % 8)
# Get bits from both arrays
bit1 = (bytes_data[byte_idx] >> bit_idx) & 1
bit2 = other_bool[i]
# OR operation
if bit1 or bit2:
checksum ^= i
return checksum
@benchmark.implementation("bytes_packed", "or")
def or_bytes_packed(data):
"""OR operation on bytes (bit-packed)"""
size = data['size']
bytes_data = data['bytes_data']
other_bool = data['other_bool']
checksum = 0
# OR each bit
for i in range(size):
byte_idx = i // 8
bit_idx = 7 - (i % 8)
# Get bits from both arrays
bit1 = (bytes_data[byte_idx] >> bit_idx) & 1
bit2 = other_bool[i]
# OR operation
if bit1 or bit2:
checksum ^= i
return checksum
# Add bitarray implementations if available
if HAS_BITARRAY:
@benchmark.implementation("bitarray", ["access", "count", "sum", "flip", "and", "or"])
def bitarray_operations(data):
"""Operations on bitarray"""
operation = data['operation']
bit_arr = data['bit_array']
if operation == 'access':
total = 0
access_count = min(1000, len(bit_arr))
step = max(1, len(bit_arr) // access_count)
for i in range(0, len(bit_arr), step):
if i < len(bit_arr) and bit_arr[i]:
total += 1
return total
elif operation == 'count':
return bit_arr.count(True)
elif operation == 'sum':
return bit_arr.count(True)
elif operation == 'flip':
result = bitarray.bitarray(bit_arr)
result.invert()
checksum = 0
for i, bit in enumerate(result):
if bit:
checksum ^= i
return checksum
elif operation == 'and':
other = bitarray.bitarray(data['other_bool'])
result = bit_arr & other
checksum = 0
for i, bit in enumerate(result):
if bit:
checksum ^= i
return checksum
elif operation == 'or':
other = bitarray.bitarray(data['other_bool'])
result = bit_arr | other
checksum = 0
for i, bit in enumerate(result):
if bit:
checksum ^= i
return checksum
# Add custom BitArray implementations if available
if HAS_CUSTOM_BITARRAY:
@benchmark.implementation("custom_bitarray", ["access", "count", "sum"])
def custom_bitarray_operations(data):
"""Operations on custom BitArray"""
operation = data['operation']
bit_arr = data['custom_bitarray']
if operation == 'access':
total = 0
access_count = min(1000, len(bit_arr))
step = max(1, len(bit_arr) // access_count)
for i in range(0, len(bit_arr), step):
if i < len(bit_arr) and bit_arr[i]:
total += 1
return total
elif operation in ['count', 'sum']:
return sum(bit_arr[i] for i in range(len(bit_arr)))
# Custom validator for boolean operations
@benchmark.validator("default")
def validate_bool_result(expected, actual):
"""Validate boolean operation results"""
# Convert results to comparable format
if hasattr(expected, 'tolist'): # array.array
expected = expected.tolist()
if hasattr(actual, 'tolist'): # array.array
actual = actual.tolist()
# Handle bitarray
if hasattr(expected, 'to01'): # bitarray
expected = [int(b) for b in expected.to01()]
if hasattr(actual, 'to01'): # bitarray
actual = [int(b) for b in actual.to01()]
# Convert booleans to ints for comparison
if isinstance(expected, list) and len(expected) > 0:
if isinstance(expected[0], bool):
expected = [int(b) for b in expected]
if isinstance(actual, list) and len(actual) > 0:
if isinstance(actual[0], bool):
actual = [int(b) for b in actual]
return expected == actual
if __name__ == "__main__":
# Parse command line args and run appropriate mode
runner = benchmark.parse_args()
runner.run()