[Erledigt] Wie könnte diese Klasse noch schneller werden: Streaming bis zu einem Boundary-String
-
@rapso: Was meinst du eigentlich mit Aliasing und Hazards?
-
Nachdem ich zunächst falsch gemessen habe, stelle ich fest, dass das Verwenden eines Doppelpuffers und memcpy statt memmove keine signifikante Performance-Verbesserung bringt.
-
__restrict bringt einiges
//VERALTET class boundary_filter : public boost::iostreams::multichar_input_filter { public: boundary_filter(std::string const &boundary) : boundary(boundary), buf(new char[boundary.size()]), eof(false), pos(boundary.size()) { kmp_init(); } boundary_filter(boundary_filter const &o) : boundary(o.boundary), buf(new char[boundary.size()]), eof(false), pos(boundary.size()) { kmp_init(); } ~boundary_filter() { delete [] buf; } private: struct eof_event {}; public: template<typename Source> std::streamsize read( Source & __restrict source, char * __restrict outbuf, std::streamsize n_) { if (eof) return -1; if (n_ <= 0) return 0; std::size_t n = std::size_t(n_); std::size_t i = 0; try { while (i < n) { std::size_t c = update(source) - pos; if (c > n - i) c = n - i; memcpy(outbuf + i, buf + pos, c); i += c; pos += c; } } catch (eof_event&) { /* snip */ eof = true; } return i ? i : -1; } private: template<typename Source> std::size_t update(Source & __restrict source) { namespace io = boost::iostreams; bool end = false; std::size_t x; while ((x = check_boundary()) == pos) { if (end || pos == 0) throw eof_event(); memmove(buf, buf + pos, boundary.size() - pos); do { std::streamsize c = io::read(source, buf + boundary.size() - pos, pos); if (c < 0) break; pos -= c; } while (pos > 0); if (pos != 0) { end = true; memmove(buf + pos, buf, boundary.size() - pos); } } return x; } void kmp_init() { kmp_next.resize(boundary.size() + 1); std::size_t i = 0; int j = -1; kmp_next[0] = -1; while (i < boundary.size()) { while (j >= 0 && boundary[j] != boundary[i]) j = kmp_next[j]; ++i; ++j; kmp_next[i] = j; } } std::size_t check_boundary() { std::size_t i = pos; int j = 0; std::size_t a = i; while (i < boundary.size()) { while (j >= 0 && buf[i] != boundary[j]) j = kmp_next[j]; ++i; ++j; if (j <= 0) a = i; } return a; } /* snip */ private: std::string const boundary; char * __restrict buf; bool eof; std::size_t pos; std::vector<int> kmp_next; };
-
Mr. N schrieb:
__restrict bringt einiges
als lustige keywords gibt's noch const, inline (bzw force inline), register, asm etc. wenn du die in kombinationen ausprobierst, bekommst du sicher konstelationen mit denen es ebenfalls schneller wird.
und ja, alternativ fuehrt man profiling auf einem optimierten build aus.
-
buf muss nicht unbedingt auf die Größe von boundary beschränkt sein - so lässt sich die Anzahl der Aufrufe von memcpy (dass bei kurzen Blöcken ohnehin für gewöhnlich nicht optimal ist) verringern. Und der Algorithmus selbst ist nicht unbedingt die beste Wahl - aber das ist auch eine Frage des konkreten Inputs.
-
rapso schrieb:
Mr. N schrieb:
__restrict bringt einiges
als lustige keywords gibt's noch const, inline (bzw force inline), register, asm etc. wenn du die in kombinationen ausprobierst, bekommst du sicher konstelationen mit denen es ebenfalls schneller wird.
und ja, alternativ fuehrt man profiling auf einem optimierten build aus.
Ich habe bereits Profiling versucht - mit unterschiedlichen optimierten Builds!
Die Zahlen waren nur nichtssagend, weil
(a) wenn ich Inlining ausschalte, wird das Ding um Faktor 20 langsamer - und dass die Relationen gleich bleiben halte ich für extrem unwahrscheinlich
(b) mit Inlining ist das ganze nur ein großer Funktionsblob.Mag sein, dass ich nicht richtig profilen kann, aber ich habs versucht.
Mir wildes zufälliges Optimieren vorzuwerfen ist auch eher Blödsinn: Ich weiß sehr genau, was __restrict bewirkt. Selbst wenn ich allerdings zufällig Optimieren würde, wäre das kein Scham, schließlich habe ich einen Benchmark.
Ich weiß übrigens sehr genau, dass register, inline, const, etc. eher wenig bringen werden.
camper schrieb:
buf muss nicht unbedingt auf die Größe von boundary beschränkt sein - so lässt sich die Anzahl der Aufrufe von memcpy (dass bei kurzen Blöcken ohnehin für gewöhnlich nicht optimal ist) verringern. Und der Algorithmus selbst ist nicht unbedingt die beste Wahl - aber das ist auch eine Frage des konkreten Inputs.
Also das memcpy lässt sich nicht vermeiden, schließlich ist outbuf von außen vorgegeben. Und eine for-Schleife ist auch bei den relativ kurzen Mustern von vielleicht 40 Zeichen langsamer als memcpy.
Wenn du die memmove meinst, ich werde mal darüber nachdenken, welche Größen für buf denn Sinn machen würden.
Was meinst du mit "der Algorithmus ist nicht optimal"? Welcher wäre denn besser? Also Boyer-Moore zum Beispiel würde AFAIK nicht gehen, weil der rückwärts matcht und das wäre hier total falsch.
Update: Ich werde nun mal versuchen, was für Ergebnisse mir AMD CodeAnalyst ausspuckt (hab ja schließlich einen AMD Prozessor), bzw. erstmal lad ich das Ding runter.
-
CodeAnalyst hab ich nicht zum Laufen gebracht, aber oprofile bringt bessere Ergebnisse als gprof:
CPU: AMD64 processors, speed 2000 MHz (estimated) Counted CPU_CLK_UNHALTED events (Cycles outside of halt state) with a unit mask of 0x00 (No unit mask) count 100000 samples % symbol name 72637 49.6809 boost::iostreams::detail::indirect_streambuf<rest::utils::boundary_filter, std::char_traits<char>, std::allocator<char>, boost::iostreams:: input>::underflow() 64166 43.8871 memcpy 3488 2.3857 std::basic_streambuf<char, std::char_traits<char> >::xsgetn(char*, long) 3202 2.1900 memmove ...Also, ich denke, das memmove ist kein relevantes Performance-Problem, dementsprechend würden auch größere Puffer nichts helfen.
Mal sehen, ob ich irgendwie noch Ergebnisse mit besserer Granularität erzeugen kann.
Update:
samples % symbol name 548120 53.3285 (anonymous namespace)::testcase2() --> 363464 35.3627 rest::utils::boundary_filter::check_boundary() 22630 2.2018 main --> 20907 2.0341 unsigned long rest::utils::boundary_filter::update<boost::iostreams::detail::linked_streambuf<char, std::char_traits<char> > >(boost::iostr eams::detail::linked_streambuf<char, std::char_traits<char> >&) 17805 1.7323 _fini 14270 1.3884 long rest::utils::boundary_filter::read<boost::iostreams::detail::linked_streambuf<char, std::char_traits<char> > >(boost::iostreams::detai l::linked_streambuf<char, std::char_traits<char> >&, char*, long) ...(Komisch, memcpy und memmove kommen nichtmal mehr vor.)
-
Ich schätze mal memmove wird intern memcpy aufrufen (z.b. wenn nicht rückwärts kopiert werden muss) - bist du sicher dass die 43% memcpy() nicht einfach daher kommen?
-
hustbaer schrieb:
Ich schätze mal memmove wird intern memcpy aufrufen (z.b. wenn nicht rückwärts kopiert werden muss) - bist du sicher dass die 43% memcpy() nicht einfach daher kommen?
Hmm kann sein, ich schau mir mal die glibc-Implementierung an.
Ich denke aber, ich sollte erstmal schauen, ob der modifizierte KMP optimal ist. Jemand ne Idee, welcher Algorithmus schneller sein könnte?
EDIT: memmove verwendet memcpy nicht. Beide verwenden aber hochinteressante Makros, die ich mir mal anschauen werde.
EDIT 2: Die Makros würden mir zwar ein paar innere ifs einsparen, leider sind die aber nicht öffentlich.
-
Ich habe mal versucht, die Lesbarkeit der Klasse zu erhöhen:
class boundary_filter : public boost::iostreams::multichar_input_filter { public: boundary_filter(std::string const &boundary) : boundary(boundary), buf(new char[boundary.size()]), eof(false), pos(boundary.size()) { kmp_init(); } boundary_filter(boundary_filter const &o) : boundary(o.boundary), buf(new char[boundary.size()]), eof(false), pos(boundary.size()) { kmp_init(); } ~boundary_filter() { delete [] buf; } private: struct eof_event {}; public: template<typename Source> std::streamsize read(Source & __restrict, char * __restrict, std::streamsize); private: template<typename Source> std::size_t update(Source & __restrict); void kmp_init(); std::size_t check_boundary(); template<typename Source> void skip_transport_padding(Source & __restrict); private: std::string const boundary; char * __restrict buf; bool eof; std::size_t pos; std::vector<int> kmp_next; }; BOOST_IOSTREAMS_PIPABLE(boundary_filter, 0) template<typename Source> std::streamsize boundary_filter::read( Source & __restrict source, char * __restrict outbuf, std::streamsize outbuf_size_) { if (eof) return -1; if (outbuf_size_ <= 0) return 0; std::size_t outbuf_size = std::size_t(outbuf_size_); std::size_t outbuf_pos = 0; try { while (outbuf_pos < outbuf_size) { std::size_t fresh_bytes = update(source) - pos; std::size_t read_bytes = std::min(fresh_bytes, outbuf_size - outbuf_pos); memcpy(outbuf + outbuf_pos, buf + pos, read_bytes); outbuf_pos += read_bytes; pos += read_bytes; } } catch (eof_event&) { skip_transport_padding(source); eof = true; } return outbuf_pos ? outbuf_pos : -1; } template<typename Source> std::size_t boundary_filter::update(Source & __restrict source) { namespace io = boost::iostreams; bool end_of_input = false; std::size_t boundary_pos; while ((boundary_pos = check_boundary()) == pos) { if (end_of_input || pos == 0) throw eof_event(); memmove(buf, buf + pos, boundary.size() - pos); do { std::streamsize input_size = io::read(source, buf + boundary.size() - pos, pos); if (input_size < 0) break; pos -= input_size; } while (pos > 0); if (pos != 0) { end_of_input = true; memmove(buf + pos, buf, boundary.size() - pos); } } return boundary_pos; } inline void boundary_filter::kmp_init() { kmp_next.resize(boundary.size() + 1); std::size_t i = 0; int j = -1; kmp_next[0] = -1; while (i < boundary.size()) { while (j >= 0 && boundary[j] != boundary[i]) j = kmp_next[j]; ++i; ++j; kmp_next[i] = j; } } inline std::size_t boundary_filter::check_boundary() { std::size_t i = pos; int j = 0; std::size_t x = i; while (i < boundary.size()) { while (j >= 0 && buf[i] != boundary[j]) j = kmp_next[j]; ++i; ++j; if (j <= 0) x = i; } return x; }
-
Das Optimierungsprojekt ist nun abgeschlossen. Vielen Dank an alle, die geholfen haben.
Das Ergebnis kann sich sehen lassen: Der Slowdown-Faktor konnte von 7-9 auf 2.8-3.2 gesenkt werden. (Der Faktor misst den Unterschied zwischen einem ungefilterten und einem gefilterten Stream. Ein Teil des Faktors entsteht allein schon dadurch, dass überhaupt ein Filter existiert.)
Ich denke, mit der jetzigen Geschwindigkeit kann man leben, zumal die Flexibilität des Filters nicht geopfert werden musste.
Also, Danke.
