Last active
August 29, 2015 14:05
-
-
Save zed/93ec2e02a22a133f5293 to your computer and use it in GitHub Desktop.
Fastest way to sum integers in text file
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| NAME := sum1Gints | |
| CC := gcc -std=c89 | |
| INPUTFILE := /tmp/1G-int-per-line | |
| .PHONY: clean run | |
| run: $(NAME) | |
| /usr/bin/time ./$< $(INPUTFILE) | |
| # Recommended gcc warning options for C, from: | |
| # http://stackoverflow.com/a/1667114 | |
| %-debug: %.c | |
| $(CC) -pedantic -Wall \ | |
| -Wno-missing-braces -Wextra -Wno-missing-field-initializers -Wformat=2 \ | |
| -Wswitch-default -Wswitch-enum -Wcast-align -Wpointer-arith \ | |
| -Wbad-function-cast -Wstrict-overflow=5 -Wstrict-prototypes -Winline \ | |
| -Wundef -Wnested-externs -Wcast-qual -Wshadow -Wunreachable-code \ | |
| -Wlogical-op -Wfloat-equal -Wstrict-aliasing=2 -Wredundant-decls \ | |
| -Wold-style-definition -Werror \ | |
| -ggdb3 \ | |
| -O0 \ | |
| -fno-omit-frame-pointer -ffloat-store -fno-common -fstrict-aliasing \ | |
| -lm -o $@ $^ | |
| %: %.c | |
| $(CC) -pedantic -O3 -DNDEBUG -flto -o $@ $^ | |
| clean: | |
| rm ./$(NAME) ./$(NAME)-debug -f | |
| # $@ - current target | |
| # $* '%'-part (works if there *is* '%' in specification) | |
| # $< first dependence | |
| # $^ all dependencies (without duplicates) |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| /** To measure time performance, run: | |
| $ make NAME=sum1Gints-maaartinus-mmap | |
| To clear file caches (as a root): | |
| # free && sync && echo 3 > /proc/sys/vm/drop_caches && free | |
| Algorithm from: | |
| http://stackoverflow.com/questions/25606833/fastest-way-to-sum-integers-in-text-file/25607155#comment40046670_25607155 | |
| mmap code is from the mmap man-page | |
| */ | |
| #include <sys/mman.h> | |
| #include <sys/stat.h> | |
| #include <fcntl.h> | |
| #include <stdio.h> | |
| #include <stdlib.h> | |
| #include <inttypes.h> | |
| #include <ctype.h> | |
| #define report_error_and_exit(msg) \ | |
| do { perror(msg); exit(EXIT_FAILURE); } while (0) | |
| int | |
| main(int argc, char *argv[]) | |
| { | |
| if (argc == 2) { | |
| uint64_t total_sum = 0; /* sum of all (nonnegative) integers in the file */ | |
| int fd = -1; | |
| struct stat sb = {0}; /* fstat result */ | |
| size_t length = 0; /* file size */ | |
| fd = open(argv[1], O_RDONLY); | |
| if (fd == -1) | |
| report_error_and_exit("open"); | |
| if (fstat(fd, &sb) == -1) /* obtain file size */ | |
| report_error_and_exit("fstat"); | |
| length = sb.st_size; | |
| if (length > 0) { | |
| int32_t partial = 0; /* hold part of the current integer that is parsed */ | |
| char *addr = mmap(NULL, length, PROT_READ, MAP_PRIVATE, fd, 0); | |
| char *p = addr; | |
| if (addr == MAP_FAILED) | |
| report_error_and_exit("mmap"); | |
| for (; p != &addr[length]; ++p) { | |
| if (isdigit(*p)) { | |
| partial = 10*partial + *p - '0'; | |
| } | |
| else if (partial) { /* non-digit found */ | |
| total_sum += partial; /* add the parsed number */ | |
| partial = 0; /* start new number */ | |
| } | |
| } | |
| } | |
| printf("%" PRIu64 "\n", total_sum); /* print result */ | |
| exit(EXIT_SUCCESS); | |
| } | |
| else { /* argc != 2 */ | |
| fprintf(stderr, "Usage: %s filename\n", argv[0]); | |
| exit(2); | |
| } | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment