5 ms·

seems like it would be worth comparing to the old "awk '!a[$0] { a[$0]=1; print }'". I would assume that such arrays are implemented internally using hash table

seems like it would be worth comparing to the old "awk '!a[$0] { a[$0]=1; print }'". I would assume that such arrays are implemented internally using hash tables. probably not as efficient as a C implementation, but the used parts of the interpreter should fit in I-cache, so it should be within a few times as fast.

majke 7y ago
Here you go: marek:~$ time (cat logs-popcount-org.txt | awk '!a[$0] {a[$0]=1; print }'|wc -l) 39057531 real 0m41.236s user 0m38.179s sys 0m5.447s So: sort: 2m, awk 41 seconds. Also, awk used 6.1G of RAM at peak.
- Hello71 7y ago
  yeah, a generic, probably pointer-heavy hash table is definitely gonna be worse on memory. I'm surprised that it's that much worse on time though, I expected it to be closer. I guess probably the cache misses are worse with such a large table though.
  - majke 7y ago
    Ok, I'll bite again: marek:~$ cat logs-popcount-org.txt | perf stat -d awk '!a[$0] { a[$0]=1; print }' > /dev/null Performance counter stats for 'awk !a[$0] { a[$0]=1; print }': 40,318.47 msec task-clock:u 0 context-switches:u 0 cpu-migrations:u 1,670,649 page-faults:u 112,979,634,215 cycles:u 93,441,976,758 instructions:u 18,990,099,679 branches:u 208,386,137 branch-misses:u 26,093,832,363 L1-dcache-loads:u 708,880,979 L1-dcache-load-misses:u 464,332,790 LLC-loads:u 245,913,835 LLC-load-misses:u 40.337768657 seconds time elapsed 36.851718000 seconds user 3.468126000 seconds sys Compare this to the optimized approach which has 57M LLC-load-misses, and 7M instructions.
    - ncmncm 7y ago
      I would welcome seeing a comparison in your environment to using the simple 1/2 GB array of bits, with no hashing or storage of IP addresses. (Extra points for hugetlb mapping.)

majke 7y ago

Here you go: marek:~$ time (cat logs-popcount-org.txt | awk '!a[$0] {a[$0]=1; print }'|wc -l) 39057531 real 0m41.236s user 0m38.179s sys 0m5.447s So: sort: 2m, awk 41 seconds. Also, awk used 6.1G of RAM at peak.

Hello71 7y ago
yeah, a generic, probably pointer-heavy hash table is definitely gonna be worse on memory. I'm surprised that it's that much worse on time though, I expected it to be closer. I guess probably the cache misses are worse with such a large table though.
- majke 7y ago
  Ok, I'll bite again: marek:~$ cat logs-popcount-org.txt | perf stat -d awk '!a[$0] { a[$0]=1; print }' > /dev/null Performance counter stats for 'awk !a[$0] { a[$0]=1; print }': 40,318.47 msec task-clock:u 0 context-switches:u 0 cpu-migrations:u 1,670,649 page-faults:u 112,979,634,215 cycles:u 93,441,976,758 instructions:u 18,990,099,679 branches:u 208,386,137 branch-misses:u 26,093,832,363 L1-dcache-loads:u 708,880,979 L1-dcache-load-misses:u 464,332,790 LLC-loads:u 245,913,835 LLC-load-misses:u 40.337768657 seconds time elapsed 36.851718000 seconds user 3.468126000 seconds sys Compare this to the optimized approach which has 57M LLC-load-misses, and 7M instructions.
  - ncmncm 7y ago
    I would welcome seeing a comparison in your environment to using the simple 1/2 GB array of bits, with no hashing or storage of IP addresses. (Extra points for hugetlb mapping.)