collab/1brc
the one billion row challenge
git clone https://git.julia.blue/collab/1brc
ff1f4de
back-to-mmap
1// cc -lnuma 2 3#define _GNU_SOURCE 4#include <errno.h> 5#include <fcntl.h> 6#include <inttypes.h> 7#include <sched.h> 8#include <stdint.h> 9#include <stdio.h> 10#include <stdlib.h> 11#include <string.h> 12#include <sys/mman.h> 13#include <sys/stat.h> 14#include <sys/statfs.h> 15#include <sys/types.h> 16#include <sys/wait.h> 17#include <unistd.h> 18 19#include <numa.h> 20#include <numaif.h> 21 22#ifndef HUGETLBFS_MAGIC 23#define HUGETLBFS_MAGIC 0x958458f6 24#endif 25 26static void die (const char * msg ) { 27int e = errno ; 28fprintf (stderr ,"%s: %s\n" ,msg ,strerror (e )); 29exit (1 ); 30} 31 32static size_t round_up_size (size_t x ,size_t a ) { 33return (x + a - 1 ) /a * a ; 34} 35 36static size_t detect_hugepage_size_from_path (const char * path ) { 37struct statfs s ; 38if (statfs (path ,& s )== 0 ) { 39if ((unsigned long )s .f_type == (unsigned long )HUGETLBFS_MAGIC && s .f_bsize > 0 ) { 40return (size_t )s .f_bsize ; 41 } 42if (s .f_bsize > 0 && (size_t )s .f_bsize >=4096 ) 43return (size_t )s .f_bsize ; 44 } 45return 2u * 1024u * 1024u ; 46} 47 48struct numa_node_info { 49int node ; 50int cpu_count ; 51cpu_set_t cpuset ; 52}; 53 54static void copy_range ( 55int fd ,size_t in_size ,void * dst ,size_t start ,size_t length 56) { 57const size_t buf_sz = 1024 * 1024 ; 58char * buf = malloc (buf_sz ); 59if (!buf )die ("malloc failed" ); 60 61if (lseek (fd , (off_t )start ,SEEK_SET )< 0 )die ("lseek(input) failed" ); 62 63size_t remaining = length ; 64size_t copied = 0 ; 65while (remaining > 0 && (start + copied )< in_size ) { 66size_t want = remaining ; 67if (want > buf_sz )want = buf_sz ; 68if (start + copied + want > in_size ) { 69want = in_size - (start + copied ); 70if (want == 0 )break ; 71 } 72 73ssize_t n = read (fd ,buf ,want ); 74if (n < 0 )die ("read failed" ); 75if (n == 0 )break ; 76 77memcpy ((char * )dst + start + copied ,buf , (size_t )n ); 78copied += (size_t )n ; 79remaining -= (size_t )n ; 80 } 81 82free (buf ); 83} 84 85static void setup_numa ( 86struct numa_node_info ** out_nodes ,int * out_nnodes ,long * out_total_weight 87) { 88if (numa_available ()< 0 ) { 89die ("NUMA requested but libnuma reports unavailable" ); 90 } 91 92int max_node = numa_max_node (); 93int nnodes = 0 ; 94 95struct numa_node_info * nodes = 96calloc ((size_t )(max_node + 1 ),sizeof (struct numa_node_info )); 97if (!nodes )die ("calloc nodes failed" ); 98 99long total_weight = 0 ; 100 101for (int n = 0 ;n <=max_node ;n ++ ) { 102if (!numa_bitmask_isbitset (numa_all_nodes_ptr ,n )) 103continue ; 104 105cpu_set_t cpuset ; 106CPU_ZERO (& cpuset ); 107 108struct bitmask * bm = numa_allocate_cpumask (); 109if (!bm )die ("numa_allocate_cpumask failed" ); 110 111if (numa_node_to_cpus (n ,bm )!= 0 ) { 112numa_free_cpumask (bm ); 113continue ; 114 } 115 116int cpu_count = 0 ; 117for (int c = 0 ;c < bm -> size ;c ++ ) { 118if (numa_bitmask_isbitset (bm ,c )) { 119CPU_SET (c ,& cpuset ); 120cpu_count ++ ; 121 } 122 } 123 124numa_free_cpumask (bm ); 125 126if (cpu_count == 0 ) 127continue ; 128 129nodes [nnodes ].node = n ; 130nodes [nnodes ].cpu_count = cpu_count ; 131nodes [nnodes ].cpuset = cpuset ; 132total_weight += cpu_count ; 133nnodes ++ ; 134 } 135 136if (nnodes == 0 ) { 137free (nodes ); 138die ("NUMA requested but no nodes with CPUs found, falling back" ); 139 } 140 141* out_nodes = nodes ; 142* out_nnodes = nnodes ; 143* out_total_weight = total_weight ; 144} 145 146int main (int argc ,char ** argv ) { 147if (argc != 3 ) { 148fprintf (stderr ,"usage: %s <input file> <output path under hugetlbfs mount>\n" ,argv [0 ]); 149return 2 ; 150 } 151 152const char * in_path = argv [1 ]; 153const char * out_path = argv [2 ]; 154 155int in_fd = open (in_path ,O_RDONLY ); 156if (in_fd < 0 )die ("open(input) failed" ); 157 158struct stat st ; 159if (fstat (in_fd ,& st )< 0 )die ("fstat(input) failed" ); 160if (!S_ISREG (st .st_mode )) { 161fprintf (stderr ,"input must be a regular file\n" ); 162return 2 ; 163 } 164 165size_t in_size = (size_t )st .st_size ; 166size_t hpsz = detect_hugepage_size_from_path (out_path ); 167size_t out_size = round_up_size (in_size ,hpsz ); 168 169int out_fd = open (out_path ,O_RDWR |O_CREAT |O_TRUNC ,0644 ); 170if (out_fd < 0 )die ("open(output) failed" ); 171 172if (ftruncate (out_fd , (off_t )out_size )< 0 )die ("ftruncate(output) failed" ); 173 174size_t flags = 0 ; 175switch (hpsz ) { 176case (2 * 1024 * 1024 ):flags = MAP_HUGE_2MB ;break ; 177case (1 * 1024 * 1024 * 1024 ):flags = MAP_HUGE_1GB ;break ; 178 } 179void * dst = mmap (NULL ,out_size ,PROT_READ |PROT_WRITE ,MAP_SHARED |MAP_HUGETLB |flags ,out_fd ,0 ); 180if (dst == MAP_FAILED )die ("mmap(output) failed" ); 181 182int use_numa = (getenv ("NUMA" )!= NULL ); 183if (!use_numa ) { 184copy_range (in_fd ,in_size ,dst ,0 ,out_size ); 185 }else { 186struct numa_node_info * nodes = NULL ; 187int nnodes = 0 ; 188long total_weight = 0 ; 189 190setup_numa (& nodes ,& nnodes ,& total_weight ); 191// Compute per-node byte ranges proportional to cpu_count 192size_t remaining = in_size ; 193size_t offset = 0 ; 194 195for (int i = 0 ;i < nnodes ;i ++ ) { 196struct numa_node_info * ni = & nodes [i ]; 197 198// Proportional share 199size_t share = 0 ; 200if (i == nnodes - 1 ) { 201// give the remainder to the last node to cover whole file 202share = remaining ; 203 }else { 204double fraction = (double )ni -> cpu_count / (double )total_weight ; 205share = (size_t )((double )in_size * fraction ); 206if (share > remaining )share = remaining ; 207 } 208 209if (share == 0 && i != nnodes - 1 ) { 210continue ; 211 } 212 213pid_t pid = fork (); 214if (pid < 0 )die ("fork failed" ); 215 216if (pid == 0 ) { 217// Child: pin to this node's CPUs and copy our range 218if (sched_setaffinity (0 ,sizeof (cpu_set_t ),& ni -> cpuset )!= 0 ) { 219die ("sched_setaffinity failed" ); 220 } 221 222copy_range (in_fd ,in_size ,dst ,offset ,share ); 223 224_exit (0 ); 225 }else { 226int status = 0 ; 227if (waitpid (pid ,& status ,0 )< 0 )die ("waitpid failure" ); 228if (!WIFEXITED (status )|| WEXITSTATUS (status )!= 0 ) { 229die ("child exited abnormally" ); 230 } 231 } 232 233offset += share ; 234if (remaining >=share )remaining -= share ; 235else remaining = 0 ; 236 } 237 238free (nodes ); 239 240if (out_size > in_size ) { 241memset ((char * )dst + in_size ,0 ,out_size - in_size ); 242 } 243 } 244 245if (msync (dst ,out_size ,MS_SYNC )< 0 )die ("msync failed" ); 246 247if (munmap (dst ,out_size )< 0 )die ("munmap failed" ); 248if (close (out_fd )< 0 )die ("close(output) failed" ); 249if (close (in_fd )< 0 )die ("close(input) failed" ); 250 251return 0 ; 252}