// Author: Pete Kirkham // Date: 2007-10-31 // wide-finder benchmark - block io, 8-wide line break + BMH prefix match algorithm, full regex. // bitmatch changed with reference to http://graphics.stanford.edu/~seander/bithacks.html#ZeroInWord #include #include #include #include #include #include #include #include #include #include #include #include #include #define BLOCK_SIZE 8096 // map for counting matches typedef std::map match_map; typedef std::pair matchling; struct order_by_second { bool operator() (const matchling& left, const matchling& right) const { return left.second > right.second; } }; typedef std::priority_queue, order_by_second> top_heap; // BMH string search // pattern must be allocated to be a multiple of 8 chars size_t prefix_search (const char* pattern, size_t pattern_length, int* table, const char* string, size_t string_length) { const char last_char(pattern[pattern_length - 1]); const size_t last_index(string_length - 1); const size_t pattern_last(pattern_length - 1); // scan pattern_length chars at a time for last char in pattern for (size_t index(0); index < last_index; ) { size_t scan(pattern_last); for (; string[index + scan] == pattern[scan]; --scan) if (scan == 0) return index; int jump(table[size_t(string[index + scan]) & 0xff]); size_t matched(pattern_last - scan); if ( jump <= matched ) ++index; else index += jump - matched; } return string_length; } #define character_range(a, b) if (line[index] < a || line[index] > b) return; ++index; #define character_equal(c) if (line[index] != c) return; ++index; // process a line of input inline void process_line (match_map& matches, const char* pattern, size_t pattern_length, int* table, const char* line, size_t line_length) { size_t match(prefix_search(pattern, pattern_length, table, line, line_length) + pattern_length); size_t index(match); if (index >= line_length - 18) return; character_range('0', '9'); character_range('0', '9'); character_range('0', '9'); character_equal('x'); character_equal('/'); character_range('0', '9'); character_range('0', '9'); character_range('0', '9'); character_range('0', '9'); character_equal('/'); character_range('0', '9'); character_range('0', '9'); character_equal('/'); character_range('0', '9'); character_range('0', '9'); character_equal('/'); while (index < line_length) { char ch(line[index]); if ((ch == '.') || (ch == '\n')) break; if (ch == ' ') { if (index > match + 18) { ++matches[std::string(line + match + 5, index - (match + 5))]; #ifdef LIST_MATCHES std::cout << std::string(line + match + 5, index - (match + 5)) << std::endl; #endif } break; } ++index; } } // find top k matches O(N log k) depending on priority_queue implementation void find_top_matches (const size_t k_desired, top_heap& top_k, const match_map& matches) { size_t least_count(0); for (match_map::const_iterator it(matches.begin()); it != matches.end(); ++it) { if (top_k.size() == k_desired) { for (++it; it != matches.end(); ++it) { if (it->second > least_count) { top_k.pop(); top_k.push(*it); least_count = top_k.top().second; } } break; } else { top_k.push(*it); } } } // main int main (int narg, char** argvp) { if (narg < 2) { std::cout << "The name of the input file is required." << std::endl; return 1; } // open the file int file(open(argvp[1], O_RDONLY)); if (!file) { std::cout << "failed to open " << argvp[1] << std::endl; return 2; } // prefix of pattern to find const char* pattern("GET /ongoing/When/"); size_t pattern_length(strlen(pattern)); // bmh table int table[256]; for (size_t scan(0); scan < 256; ++scan) table[scan] = pattern_length; for (size_t scan(0); scan < pattern_length - 1; ++scan) table[size_t(pattern[scan])&0xff] = pattern_length - 1 - scan; // block IO // for splitting lines, we move any trailing part line to the start of // memory then read data into the area following it uint64_t mem[BLOCK_SIZE/4]; // use wider type to ensure alignment char* buf((char*)mem); ssize_t bytes_read; size_t bytes_carried(0); // count of matching lines match_map matches; while ((bytes_read = read(file, buf + bytes_carried, BLOCK_SIZE)) > 0) { size_t chunk_length(bytes_carried + bytes_read); size_t line_start(0); // scan for line breaks, 8 chars at a time - on x64, you can do 16, // IIRC on G5 32, using machine specific SIMD instructions, but this is // designed for portability between 64 bit unix variants. for (size_t i(0); i < chunk_length; i += 8) { uint64_t data(*((uint64_t*)(buf+i))); data = (data ^ 0x0a0a0a0a0a0a0a0aLL); if ((data - 0x0101010101010101LL) & ~data & 0x8080808080808080LL) { // you can do without this scan - if you know machine endianness, then // one of the eight non-zero values of data will give the index for (; i < chunk_length; ++i) { if (buf[i] == '\n') { size_t line_length(i - line_start); const char* line(buf + line_start); #ifdef ECHO_LINES buf[i] = '\0'; std::cout << buf + line_start << std::endl; #endif process_line(matches, pattern, pattern_length, table, line, line_length); line_start = i+1; i &= ~7; break; // assumes there are no lines < 8 characters } } } } // copy trailing data to start of alternate block // assumes that a line is never more than half a block long bytes_carried = chunk_length - line_start; memcpy(buf, buf + line_start, bytes_carried); } // if there is any last line, process that if (bytes_carried) { process_line(matches, pattern, pattern_length, table, buf, bytes_carried); } close(file); const size_t k_desired(10); top_heap top_k; find_top_matches(k_desired, top_k, matches); // output them, reversing the order in the heap std::vector out_list; while (!top_k.empty()) { out_list.push_back(top_k.top()); top_k.pop(); } std::reverse(out_list.begin(), out_list.end()); for (std::vector::const_iterator it(out_list.begin()); it != out_list.end(); ++it) { std::cout << it->second << ": " << it->first << std::endl; } return 0; }