[devel] [PATCH 0/3] optimize rpmsetcmp()

[devel] [PATCH 0/3] optimize rpmsetcmp()

[@ 2010-11-25 22:04 UTC (permalink / raw)]

[devel] [PATCH 1/3] set.c: use packed bitmap for bit vector

[@ 2010-11-25 22:04 UTC (permalink / raw)]

[devel] [PATCH 2/3] set.c: optimize putbits()

[@ 2010-11-25 22:04 UTC (permalink / raw)]

[devel] [PATCH 3/3] set.c: optimize decode_golomb()

[@ 2010-11-25 22:04 UTC (permalink / raw)]

Re: [devel] [PATCH 0/3] optimize rpmsetcmp()

[@ 2010-11-26 8:35 UTC (permalink / raw)]

Re: [devel] [PATCH 0/3] optimize rpmsetcmp()

[@ 2010-11-30 0:35 UTC (permalink / raw)]

Re: [devel] [PATCH 0/3] optimize rpmsetcmp()

[@ 2010-12-02 21:48 UTC (permalink / raw)]

Re: [devel] [PATCH 0/3] optimize rpmsetcmp()

[@ 2010-12-04 13:02 UTC (permalink / raw)]

Re: [devel] [PATCH 0/3] optimize rpmsetcmp()

[@ 2010-12-04 16:30 UTC (permalink / raw)]

Re: [devel] [PATCH 0/3] optimize rpmsetcmp()

[@ 2010-12-04 16:55 UTC (permalink / raw)]

Re: [devel] [PATCH 0/3] optimize rpmsetcmp()

[Alexey Tourbin]

On Tue, Nov 30, 2010 at 03:35:42AM +0300, Dmitry V. Levin wrote:
> On Fri, Nov 26, 2010 at 10:35:37AM +0200, Kirill A. Shutemov wrote:
> > apt-shell < /dev/null

> Not so amazing as on your test platform, but awesome anyway.
> I'm going to apply these patches.
> If anybody has objections, please speak up now.

The objection is, why do you think the problem is with here, not with apt?
Go yonder and optimize apt!

> -- 
> ldv

Re: [devel] [PATCH 0/3] optimize rpmsetcmp()

[Dmitry V. Levin]

[-- Attachment #1: Type: text/plain, Size: 660 bytes --]

On Sat, Dec 04, 2010 at 06:06:18PM +0300, Alexey Tourbin wrote:
> On Tue, Nov 30, 2010 at 03:35:42AM +0300, Dmitry V. Levin wrote:
> > On Fri, Nov 26, 2010 at 10:35:37AM +0200, Kirill A. Shutemov wrote:
> > > apt-shell < /dev/null
> 
> > Not so amazing as on your test platform, but awesome anyway.
> > I'm going to apply these patches.
> > If anybody has objections, please speak up now.
> 
> The objection is, why do you think the problem is with here, not with apt?
> Go yonder and optimize apt!

It was rpm that was changed to work 10x times slower, not apt.
But apt certainly could be made better, so feel free to optimize it.


-- 
ldv

[-- Attachment #2: Type: application/pgp-signature, Size: 198 bytes --]

Re: [devel] [PATCH 0/3] optimize rpmsetcmp()

[Alexey Tourbin]

On Sat, Dec 04, 2010 at 07:29:11PM +0300, Dmitry V. Levin wrote:
> On Sat, Dec 04, 2010 at 06:06:18PM +0300, Alexey Tourbin wrote:
> > On Tue, Nov 30, 2010 at 03:35:42AM +0300, Dmitry V. Levin wrote:
> > > On Fri, Nov 26, 2010 at 10:35:37AM +0200, Kirill A. Shutemov wrote:
> > > > apt-shell < /dev/null
> > 
> > > Not so amazing as on your test platform, but awesome anyway.
> > > I'm going to apply these patches.
> > > If anybody has objections, please speak up now.
> > 
> > The objection is, why do you think the problem is with here, not with apt?
> > Go yonder and optimize apt!
> 
> It was rpm that was changed to work 10x times slower, not apt.
> But apt certainly could be made better, so feel free to optimize it.

RPM goes reasonably fast, and it's not exactly "slower".
Something that might be called unreasonable is behind the RPM. 

I can't see why rpm is now 10x times slower.
Slower compared to... what?

> -- 
> ldv

Re: [devel] [PATCH 0/3] optimize rpmsetcmp()

[Dmitry V. Levin]

[-- Attachment #1: Type: text/plain, Size: 1351 bytes --]

On Sat, Dec 04, 2010 at 07:42:40PM +0300, Alexey Tourbin wrote:
> On Sat, Dec 04, 2010 at 07:29:11PM +0300, Dmitry V. Levin wrote:
> > On Sat, Dec 04, 2010 at 06:06:18PM +0300, Alexey Tourbin wrote:
> > > On Tue, Nov 30, 2010 at 03:35:42AM +0300, Dmitry V. Levin wrote:
> > > > On Fri, Nov 26, 2010 at 10:35:37AM +0200, Kirill A. Shutemov wrote:
> > > > > apt-shell < /dev/null
> > > 
> > > > Not so amazing as on your test platform, but awesome anyway.
> > > > I'm going to apply these patches.
> > > > If anybody has objections, please speak up now.
> > > 
> > > The objection is, why do you think the problem is with here, not with apt?
> > > Go yonder and optimize apt!
> > 
> > It was rpm that was changed to work 10x times slower, not apt.
> > But apt certainly could be made better, so feel free to optimize it.
> 
> RPM goes reasonably fast, and it's not exactly "slower".
> Something that might be called unreasonable is behind the RPM. 
> 
> I can't see why rpm is now 10x times slower.
> Slower compared to... what?

You cannot dismiss arguments so freely.  The abovementioned command
"apt-shell < /dev/null" from apt-0.5.15lorg2-alt33 works 10x times slower
after update from librpm-4.0.4-alt98.45 to librpm-4.0.4-alt98.49.
No matter how unreasonable apt is, it was rpm update that slowed it down.


-- 
ldv

[-- Attachment #2: Type: application/pgp-signature, Size: 198 bytes --]

Re: [devel] [PATCH 0/3] optimize rpmsetcmp()

[Alexey Tourbin]

On Sat, Dec 04, 2010 at 07:52:44PM +0300, Dmitry V. Levin wrote:
> > RPM goes reasonably fast, and it's not exactly "slower".
> > Something that might be called unreasonable is behind the RPM. 
> > 
> > I can't see why rpm is now 10x times slower.
> > Slower compared to... what?
> 
> You cannot dismiss arguments so freely.  The abovementioned command
> "apt-shell < /dev/null" from apt-0.5.15lorg2-alt33 works 10x times slower
> after update from librpm-4.0.4-alt98.45 to librpm-4.0.4-alt98.49.
> No matter how unreasonable apt is, it was rpm update that slowed it down.

Okay, what's the exact reason everything went 10x times slower?

> -- 
> ldv

Re: [devel] [PATCH 0/3] optimize rpmsetcmp()

[Dmitry V. Levin]

[-- Attachment #1: Type: text/plain, Size: 806 bytes --]

On Sat, Dec 04, 2010 at 08:05:57PM +0300, Alexey Tourbin wrote:
> On Sat, Dec 04, 2010 at 07:52:44PM +0300, Dmitry V. Levin wrote:
> > > RPM goes reasonably fast, and it's not exactly "slower".
> > > Something that might be called unreasonable is behind the RPM. 
> > > 
> > > I can't see why rpm is now 10x times slower.
> > > Slower compared to... what?
> > 
> > You cannot dismiss arguments so freely.  The abovementioned command
> > "apt-shell < /dev/null" from apt-0.5.15lorg2-alt33 works 10x times slower
> > after update from librpm-4.0.4-alt98.45 to librpm-4.0.4-alt98.49.
> > No matter how unreasonable apt is, it was rpm update that slowed it down.
> 
> Okay, what's the exact reason everything went 10x times slower?

Huge amount of new set-versioned dependencies.


-- 
ldv

[-- Attachment #2: Type: application/pgp-signature, Size: 198 bytes --]

Re: [devel] [PATCH 0/3] optimize rpmsetcmp()

[Alexey Tourbin]

On Sat, Dec 04, 2010 at 08:52:00PM +0300, Dmitry V. Levin wrote:
> On Sat, Dec 04, 2010 at 08:05:57PM +0300, Alexey Tourbin wrote:
> > On Sat, Dec 04, 2010 at 07:52:44PM +0300, Dmitry V. Levin wrote:
> > > > RPM goes reasonably fast, and it's not exactly "slower".
> > > > Something that might be called unreasonable is behind the RPM. 
> > > > 
> > > > I can't see why rpm is now 10x times slower.
> > > > Slower compared to... what?
> > > 
> > > You cannot dismiss arguments so freely.  The abovementioned command
> > > "apt-shell < /dev/null" from apt-0.5.15lorg2-alt33 works 10x times slower
> > > after update from librpm-4.0.4-alt98.45 to librpm-4.0.4-alt98.49.
> > > No matter how unreasonable apt is, it was rpm update that slowed it down.
> > 
> > Okay, what's the exact reason everything went 10x times slower?
> Huge amount of new set-versioned dependencies.

It's not exactly "huge", as it is predictably associated with the number
of shared libraries in use.  Also, I remember someone wondering about
"gosh, such a long version".  And he felt not that the library was
exporting too many symbols, though.  You see the pattern: the library
was okay.

There is indeed a considerable amount of new set-version dependencies.
And I never promised them to be a free lunch, or as cheap as strcmp().
Special compression routines (simplified Golomb-Rice encoding/decoding)
have been crafted to make set-versions shorter.  They are very cheap
(as compared to general-purpose compression routines such as found in
zlib), but they are still not free.

So the whole talk is that there's a price.  I believe that the price
is very affordable (or, at least, it could've been much worse).

Now as to apt misbehavior.  "You cannot dismiss arguments so freely."
What you urge to do is to cut down the price even more.  But there is
clearly something wrong with apt, as it tries to resolve every single
dependency upon every startup.  And, fortunately, it takes only a few
seconds!

> -- 
> ldv

Re: [devel] [PATCH 0/3] optimize rpmsetcmp()

[Dmitry V. Levin]

[-- Attachment #1: Type: text/plain, Size: 700 bytes --]

On Sun, Dec 05, 2010 at 12:28:31AM +0300, Alexey Tourbin wrote:
[...]
> What you urge to do is to cut down the price even more.  But there is
> clearly something wrong with apt, as it tries to resolve every single
> dependency upon every startup.  And, fortunately, it takes only a few
> seconds!

It will take twice or trice longer time when _all_ packages with ELF
files will get their set-versioned dependencies, so I expect apt-get
startup will eventually be about 10x slower again (compared to 5.1 branch).

apt-rpm indeed calls rpmRangesOverlap() too many times, it's common
knowledge.  Unfortunately, stating this fact isn't sufficient to make
apt-rpm work faster.


-- 
ldv

[-- Attachment #2: Type: application/pgp-signature, Size: 198 bytes --]

Re: [devel] [PATCH 0/3] optimize rpmsetcmp()

[Alexey Tourbin]

On Sun, Dec 05, 2010 at 02:26:44AM +0300, Dmitry V. Levin wrote:
> On Sun, Dec 05, 2010 at 12:28:31AM +0300, Alexey Tourbin wrote:
> [...]
> > What you urge to do is to cut down the price even more.  But there is
> > clearly something wrong with apt, as it tries to resolve every single
> > dependency upon every startup.  And, fortunately, it takes only a few
> > seconds!
> 
> It will take twice or trice longer time when _all_ packages with ELF
> files will get their set-versioned dependencies, so I expect apt-get
> startup will eventually be about 10x slower again (compared to 5.1 branch).
> 
> apt-rpm indeed calls rpmRangesOverlap() too many times, it's common
> knowledge.  Unfortunately, stating this fact isn't sufficient to make
> apt-rpm work faster.

So what do you think?  There's a possibility to change bitv[] to bitmap,
per Kirill's proposal.  That mighit yield about, say 30% user time cutdown.
However, note that apt is not only eager for user time.  System time is
being spent with splendor as well.

Personally, I like bitv[], and I don't like something like <sys/select.h> stuff.

> -- 
> ldv

Re: [devel] [PATCH 0/3] optimize rpmsetcmp()

[Dmitry V. Levin]

[-- Attachment #1: Type: text/plain, Size: 1501 bytes --]

On Sun, Dec 05, 2010 at 02:41:31AM +0300, Alexey Tourbin wrote:
> On Sun, Dec 05, 2010 at 02:26:44AM +0300, Dmitry V. Levin wrote:
> > On Sun, Dec 05, 2010 at 12:28:31AM +0300, Alexey Tourbin wrote:
> > [...]
> > > What you urge to do is to cut down the price even more.  But there is
> > > clearly something wrong with apt, as it tries to resolve every single
> > > dependency upon every startup.  And, fortunately, it takes only a few
> > > seconds!
> > 
> > It will take twice or trice longer time when _all_ packages with ELF
> > files will get their set-versioned dependencies, so I expect apt-get
> > startup will eventually be about 10x slower again (compared to 5.1 branch).
> > 
> > apt-rpm indeed calls rpmRangesOverlap() too many times, it's common
> > knowledge.  Unfortunately, stating this fact isn't sufficient to make
> > apt-rpm work faster.
> 
> So what do you think?  There's a possibility to change bitv[] to bitmap,
> per Kirill's proposal.  That mighit yield about, say 30% user time cutdown.

30% is a bit optimistic, according to my measurements.

> However, note that apt is not only eager for user time.  System time is
> being spent with splendor as well.

System time takes only about 15% of elapsed time, according to my
measurements.

> Personally, I like bitv[], and I don't like something like <sys/select.h> stuff.

When performance is the issue, there should be a good rationale to choose
the approach that works slower.


-- 
ldv

[-- Attachment #2: Type: application/pgp-signature, Size: 198 bytes --]

Re: [devel] [PATCH 0/3] optimize rpmsetcmp()

[Alexey Tourbin]

On Sun, Dec 05, 2010 at 03:03:16AM +0300, Dmitry V. Levin wrote:
> > > apt-rpm indeed calls rpmRangesOverlap() too many times, it's common
> > > knowledge.  Unfortunately, stating this fact isn't sufficient to make
> > > apt-rpm work faster.
> > 
> > So what do you think?  There's a possibility to change bitv[] to bitmap,
> > per Kirill's proposal.  That mighit yield about, say 30% user time cutdown.
> 
> 30% is a bit optimistic, according to my measurements.
> 
> > However, note that apt is not only eager for user time.  System time is
> > being spent with splendor as well.
> 
> System time takes only about 15% of elapsed time, according to my
> measurements.

Under VirtualBox, which seems to become a common hardware nowadays,
system time is somewhat more noticable.

> > Personally, I like bitv[], and I don't like something like <sys/select.h> stuff.
> 
> When performance is the issue, there should be a good rationale to choose
> the approach that works slower.

There are other reasons, such as keeping the code comprehensible (at the
expense of some runtime penalties).  I think the concept of bitv[] is
crucial for understanding the code, and it helps to keep the code clean
and self-evident.  Replacing bitv[] with bitmap might be a major trade-off
for the sake of performance.  Or might not.

Re: [devel] [PATCH 0/3] optimize rpmsetcmp()

[Michael Shigorin]

On Sun, Dec 05, 2010 at 03:21:15AM +0300, Alexey Tourbin wrote:
> I think the concept of bitv[] is crucial for understanding the code

README.set?

-- 
 ---- WBR, Michael Shigorin <mike@altlinux.ru>
  ------ Linux.Kiev http://www.linux.kiev.ua/

Re: [devel] [PATCH 0/3] optimize rpmsetcmp()

[Dmitry V. Levin]

[-- Attachment #1: Type: text/plain, Size: 513 bytes --]

On Sun, Dec 05, 2010 at 03:21:15AM +0300, Alexey Tourbin wrote:
> There are other reasons, such as keeping the code comprehensible (at the
> expense of some runtime penalties).  I think the concept of bitv[] is
> crucial for understanding the code, and it helps to keep the code clean
> and self-evident.  Replacing bitv[] with bitmap might be a major trade-off
> for the sake of performance.  Or might not.

Storing one byte per bit is crucial for understanding the code?
What a nonsense!


-- 
ldv

[-- Attachment #2: Type: application/pgp-signature, Size: 198 bytes --]

Re: [devel] [PATCH 0/3] optimize rpmsetcmp()

[Alexey Tourbin]

The answer is: no.
The reason is: compilcated.
The explanation is:
  Don't try to improve my code.

On Fri, Nov 26, 2010 at 12:04:23AM +0200, Kirill A. Shutsemov wrote:
> From: Kirill A. Shutemov <kirill@shutemov.name>
> 
> Tested on Intel Core2 Duo P9500, 3GiB RAM. i586.
> 
> rpm-4.0.4-alt100.4:
> 
>  Performance counter stats for 'apt-cache unmet' (10 runs):
> 
>         3396.569863  task-clock-msecs         #      1.000 CPUs    ( +-   0.018% )
>                  12  context-switches         #      0.000 M/sec   ( +-   9.296% )
>                   5  CPU-migrations           #      0.000 M/sec   ( +-  21.414% )
>                9680  page-faults              #      0.003 M/sec   ( +-   0.002% )
>          8525321008  cycles                   #   2509.980 M/sec   ( +-   0.016% )  (scaled from 33.34%)
>          7937229883  instructions             #      0.931 IPC     ( +-   0.041% )  (scaled from 50.00%)
>          1468168069  branches                 #    432.250 M/sec   ( +-   0.014% )  (scaled from 49.99%)
>           257179182  branch-misses            #     17.517 %       ( +-   0.047% )  (scaled from 50.01%)
>            26275740  cache-references         #      7.736 M/sec   ( +-   0.114% )  (scaled from 33.35%)
>              350852  cache-misses             #      0.103 M/sec   ( +-   1.127% )  (scaled from 33.35%)
> 
>         3.398038183  seconds time elapsed   ( +-   0.018% )
> 
> rpm-4.0.4-alt100.4 + patchset:
> 
>  Performance counter stats for 'apt-cache unmet' (10 runs):
> 
>         2010.112427  task-clock-msecs         #      1.000 CPUs    ( +-   0.038% )
>                   8  context-switches         #      0.000 M/sec   ( +-  17.232% )
>                   4  CPU-migrations           #      0.000 M/sec   ( +-  21.237% )
>                9675  page-faults              #      0.005 M/sec   ( +-   0.005% )
>          5043579686  cycles                   #   2509.103 M/sec   ( +-   0.041% )  (scaled from 33.32%)
>          5567840605  instructions             #      1.104 IPC     ( +-   0.021% )  (scaled from 50.00%)
>          1028369972  branches                 #    511.598 M/sec   ( +-   0.016% )  (scaled from 50.00%)
>            94986026  branch-misses            #      9.237 %       ( +-   0.080% )  (scaled from 50.03%)
>            16227132  cache-references         #      8.073 M/sec   ( +-   0.303% )  (scaled from 33.36%)
>              323117  cache-misses             #      0.161 M/sec   ( +-   1.241% )  (scaled from 33.34%)
> 
>         2.011050788  seconds time elapsed   ( +-   0.044% )
> 
> Kirill A. Shutemov (3):
>   set.c: use packed bitmap for bit vector
>   set.c: optimize putbits()
>   set.c: optimize decode_golomb()
> 
>  lib/set.c |  186 ++++++++++++++++++++++++++++++++++++++----------------------
>  1 files changed, 118 insertions(+), 68 deletions(-)
> 
> -- 
> 1.7.3.2

Re: [devel] [PATCH 0/3] optimize rpmsetcmp()

[Dmitry V. Levin]

[-- Attachment #1: Type: text/plain, Size: 408 bytes --]

On Sun, Dec 05, 2010 at 04:24:51AM +0300, Alexey Tourbin wrote:
> The answer is: no.
> The reason is: compilcated.
> The explanation is:
>   Don't try to improve my code.

Your pride makes you blind: you cannot grasp the idea that your code
has a room for optimization :(.  That weakens all your reasoning.
Note that somebody has to support your code when you are missing for
months.


-- 
ldv

[-- Attachment #2: Type: application/pgp-signature, Size: 198 bytes --]

Re: [devel] [PATCH 0/3] optimize rpmsetcmp()

[Alexey Tourbin]

On Sun, Dec 05, 2010 at 02:18:10PM +0300, Dmitry V. Levin wrote:
> On Sun, Dec 05, 2010 at 04:24:51AM +0300, Alexey Tourbin wrote:
> > The answer is: no.
> > The reason is: compilcated.
> > The explanation is:
> >   Don't try to improve my code.
> 
> Your pride makes you blind: you cannot grasp the idea that your code
> has a room for optimization :(.  That weakens all your reasoning.

Indeed, as for set.c, I exercise djb-like approach: either show me
a major problem, or, basically, no way.  However, the code is released
under GPL and LGPL - you can make changes on your own (and I can revert
them later).

> Note that somebody has to support your code when you are missing for
> months.

I am now tempted to say that there is no need to support my code.
And I'm not missing for months - rather, I can't speak in a low mood.

> -- 
> ldv

Re: [devel] [PATCH 0/3] optimize rpmsetcmp()

[Michael Shigorin]

On Sun, Dec 05, 2010 at 04:24:51AM +0300, Alexey Tourbin wrote:
> The explanation is:
>   Don't try to improve my code.

Дык тормозит же ж.  И на сборочнице, и на localhost.
Приходится дольше сидеть в коридоре у розетки,
чтоб собрать тестовую исошку.

-- 
 ---- WBR, Michael Shigorin <mike@altlinux.ru>
  ------ Linux.Kiev http://www.linux.kiev.ua/

Re: [devel] [PATCH 0/3] optimize rpmsetcmp()

[Alexey Tourbin]

On Sun, Dec 05, 2010 at 02:39:48PM +0200, Michael Shigorin wrote:
> On Sun, Dec 05, 2010 at 04:24:51AM +0300, Alexey Tourbin wrote:
> > The explanation is:
> >   Don't try to improve my code.
> 
> Дык тормозит же ж.  И на сборочнице, и на localhost.
> Приходится дольше сидеть в коридоре у розетки,
> чтоб собрать тестовую исошку.

4.0.4-alt100.3 -> 4.0.4-alt100.5 примерно в 4 раза быстрее.
Меркантильные соображения тут не нужны.  Вопрос по сути кода
остается - стоит ли переходить от 'char bitv[]' к битовой шкале.
С точки зрения прозрачности кода - не стоит.  С точки зрения
скорости исполнения - выгода заметная, но не офигительная.

К тому же Кирилл там использует целочисленное деление, а оно
выполняется не везде дёшево.  Хотя, с константой в знаменателе,
gcc скорее всего заменяет деление на сдвиг.  Но это уже детали.

> -- 
>  ---- WBR, Michael Shigorin <mike@altlinux.ru>
>   ------ Linux.Kiev http://www.linux.kiev.ua/

Re: [devel] [PATCH 0/3] optimize rpmsetcmp()

[Dmitry V. Levin]

[-- Attachment #1: Type: text/plain, Size: 1060 bytes --]

On Sun, Dec 05, 2010 at 03:58:49PM +0300, Alexey Tourbin wrote:
> On Sun, Dec 05, 2010 at 02:39:48PM +0200, Michael Shigorin wrote:
> > On Sun, Dec 05, 2010 at 04:24:51AM +0300, Alexey Tourbin wrote:
> > > The explanation is:
> > >   Don't try to improve my code.
> > 
> > Дык тормозит же ж.  И на сборочнице, и на localhost.
> > Приходится дольше сидеть в коридоре у розетки,
> > чтоб собрать тестовую исошку.
> 
> 4.0.4-alt100.3 -> 4.0.4-alt100.5 примерно в 4 раза быстрее.
> Меркантильные соображения тут не нужны.

Да нет же, по сравнению с 5.1 пользователь видит не ускорение в 4 раза, а
замедление в 4 раза, и по мере пересборки Сизифа с set-versioned deps это
замедление будет ещё заметнее.  Например, во время тестовой пересборки
это замедление выливается в несколько часов машинного времени.
Не надо делать вид, что проблемы нет.  Вот только одной лишь
оптимизацией lib/set.c эту проблему не решить.

> Вопрос по сути кода
> остается - стоит ли переходить от 'char bitv[]' к битовой шкале.

А вот это уже детали.


-- 
ldv

[-- Attachment #2: Type: application/pgp-signature, Size: 198 bytes --]