From f903069c139df58d1ba855f7cf02c4a2d4e51dc3 Mon Sep 17 00:00:00 2001 From: Julian Andres Klode Date: Tue, 27 Sep 2016 18:28:55 +0200 Subject: Optimize VersionHash() to not need temporary copy of input Stop copying stuff, and just parse the bytes one by-one to the newly created AddCRC16Byte. This improves the instruction count for an update run from 720,850,121 to 455,801,749 according to callgrind. --- apt-pkg/contrib/crc-16.cc | 4 ++++ apt-pkg/contrib/crc-16.h | 1 + apt-pkg/deb/deblistparser.cc | 20 ++++++-------------- 3 files changed, 11 insertions(+), 14 deletions(-) (limited to 'apt-pkg') diff --git a/apt-pkg/contrib/crc-16.cc b/apt-pkg/contrib/crc-16.cc index f5df2d8b1..250d7664a 100644 --- a/apt-pkg/contrib/crc-16.cc +++ b/apt-pkg/contrib/crc-16.cc @@ -64,6 +64,10 @@ static unsigned short const crc16_table[256] = /* Recompute the FCS with one more character appended. */ #define CalcFCS(fcs, c) (((fcs) >> 8) ^ crc16_table[((fcs) ^ (c)) & 0xff]) +unsigned short AddCRC16Byte(unsigned short fcs, unsigned char byte) +{ + return CalcFCS(fcs, byte); +} unsigned short AddCRC16(unsigned short fcs, void const *Buf, unsigned long long len) { diff --git a/apt-pkg/contrib/crc-16.h b/apt-pkg/contrib/crc-16.h index 08acdafb7..6cc3556c6 100644 --- a/apt-pkg/contrib/crc-16.h +++ b/apt-pkg/contrib/crc-16.h @@ -13,6 +13,7 @@ #include #define INIT_FCS 0xffff +unsigned short AddCRC16Byte(unsigned short fcs, unsigned char byte) APT_CONST; unsigned short AddCRC16(unsigned short fcs, void const *buf, unsigned long long len) APT_PURE; diff --git a/apt-pkg/deb/deblistparser.cc b/apt-pkg/deb/deblistparser.cc index 549e75952..15251bce4 100644 --- a/apt-pkg/deb/deblistparser.cc +++ b/apt-pkg/deb/deblistparser.cc @@ -353,7 +353,6 @@ unsigned short debListParser::VersionHash() pkgTagSection::Key::Breaks, pkgTagSection::Key::Replaces}; unsigned long Result = INIT_FCS; - char S[1024]; for (auto I : Sections) { const char *Start; @@ -363,23 +362,16 @@ unsigned short debListParser::VersionHash() /* Strip out any spaces from the text, this undoes dpkgs reformatting of certain fields. dpkg also has the rather interesting notion of - reformatting depends operators < -> <= */ - char *J = S; - for (; Start != End && (J - S) < sizeof(S); ++Start) + reformatting depends operators < -> <=, so we drop all = from the + string to make that not matter. */ + for (; Start != End; ++Start) { - if (isspace_ascii(*Start) != 0) + if (isspace_ascii(*Start) != 0 || *Start == '=') continue; - *J++ = tolower_ascii_unsafe(*Start); - - /* Normalize <= to < and >= to >. This is the wrong way around, but - * more efficient that the right way. And since we're only hashing - * it does not matter which way we normalize. */ - if ((*Start == '<' || *Start == '>') && Start[1] == '=') { - Start++; - } + Result = AddCRC16Byte(Result, tolower_ascii_unsafe(*Start)); } - Result = AddCRC16(Result,S,J - S); + } return Result; -- cgit v1.2.3