Debian Bug report logs - #294853
dialog: Bad performance with large menus.

version graph

Package: dialog; Maintainer for dialog is Santiago Vila <sanvila@debian.org>; Source for dialog is src:dialog.

Reported by: Lasse Kantola <Lasse.Kantola@iki.fi>

Date: Fri, 11 Feb 2005 22:18:07 UTC

Severity: minor

Found in version 1.0-20050206-1

Fixed in version dialog/1.0-20051107-1

Done: Santiago Vila <sanvila@debian.org>

Bug is archived. No further changes may be made.

Forwarded to Thomas Dickey <dickey@his.com>

Toggle useless messages

View this report as an mbox folder, status mbox, maintainer mbox


Report forwarded to debian-bugs-dist@lists.debian.org, Santiago Vila <sanvila@debian.org>:
Bug#294853; Package dialog. Full text and rfc822 format available.

Acknowledgement sent to Lasse Kantola <Lasse.Kantola@iki.fi>:
New Bug report received and forwarded. Copy sent to Santiago Vila <sanvila@debian.org>. Full text and rfc822 format available.

Message #5 received at submit@bugs.debian.org (full text, mbox):

From: Lasse Kantola <Lasse.Kantola@iki.fi>
To: Debian Bug Tracking System <submit@bugs.debian.org>
Subject: dialog: Bad performance with large menus.
Date: Sat, 12 Feb 2005 00:07:49 +0200
Package: dialog
Version: 1.0-20050206-1
Severity: minor


To reproduce the problem set LC_ALL to some locale (not C or POSIX)
and execute:
  
    dialog --menu text 0 0 0 $(seq 1 1000)

Scroll down by pressing the down arrow key. The scrolling is
extremely slow and consumes a lot of CPU. Increase the "1000"
in the command to see the effect better.

It seems that the cache_list in the inputstr.c module scales
very badly. Below is a part of the gprof output:


Each sample counts as 0.01 seconds.
  %   cumulative   self              self     total           
 time   seconds   seconds    calls   s/call   s/call  name    
 51.35    126.42   126.42    45341     0.00     0.00  load_cache
 48.37    245.49   119.07    45341     0.00     0.00  save_cache


-- System Information:
Debian Release: 3.1
  APT prefers unstable
  APT policy: (500, 'unstable')
Architecture: i386 (i686)
Kernel: Linux 2.6.9
Locale: LANG=C, LC_CTYPE=fi_FI.UTF-8 (charmap=UTF-8)

Versions of packages dialog depends on:
ii  debianutils                 2.11.2       Miscellaneous utilities specific t
ii  libc6                       2.3.2.ds1-20 GNU C Library: Shared libraries an
ii  libncursesw5                5.4-4        Shared libraries for terminal hand

-- no debconf information



Message sent on to Lasse Kantola <Lasse.Kantola@iki.fi>:
Bug#294853. Full text and rfc822 format available.

Message #8 received at 294853-submitter@bugs.debian.org (full text, mbox):

From: Thomas Dickey <dickey@radix.net>
To: 294853-submitter@bugs.debian.org
Subject: Re: Bug#294853: dialog: Bad performance with large menus.
Date: Sat, 12 Feb 2005 17:49:49 -0500
[Message part 1 (text/plain, inline)]
On Fri, Feb 11, 2005 at 11:30:13PM +0100, Lasse Kantola wrote:
 
> It seems that the cache_list in the inputstr.c module scales
> very badly. Below is a part of the gprof output:

I hadn't noticed (sorry).  Though I was aware that it could be a problem, it
hadn't become an issue til now.

Originally the caching was for input editing, but was useful for miscellaneous
computations - which would explain this.  It's likely that I can improve
performance by associating a cache with each string to be adjusted, rather than
reinitializing the cache for each call.
 
> Each sample counts as 0.01 seconds.
>   %   cumulative   self              self     total           
>  time   seconds   seconds    calls   s/call   s/call  name    
>  51.35    126.42   126.42    45341     0.00     0.00  load_cache
>  48.37    245.49   119.07    45341     0.00     0.00  save_cache

on my machine, I can get it up to about 9% CPU usage by this test...

-- 
Thomas E. Dickey
http://invisible-island.net
ftp://invisible-island.net
[Message part 2 (application/pgp-signature, inline)]

Information stored:
Bug#294853; Package dialog. Full text and rfc822 format available.

Acknowledgement sent to Lasse Kantola <Lasse.Kantola@iki.fi>:
Extra info received and filed, but not forwarded. Full text and rfc822 format available.

Message #13 received at 294853-quiet@bugs.debian.org (full text, mbox):

From: Lasse Kantola <Lasse.Kantola@iki.fi>
To: Thomas Dickey <dickey@radix.net>, 294853-quiet@bugs.debian.org
Subject: Re: Bug#294853: dialog: Bad performance with large menus.
Date: Sun, 13 Feb 2005 11:08:46 +0200
On Sat, 12 Feb 2005 17:49:49 -0500 Thomas Dickey <dickey@radix.net> wrote:
>
> I hadn't noticed (sorry).  Though I was aware that it could be a
> problem, it hadn't become an issue til now.
>

In my use case, I use dialog to select one line out of about 1000 lines. I
think that dialog was never meant to handle so big menus, but it would be
of course very nice if the performance was independent of the size of the
menu. Now that I think of it, I could have as well set the bug severity to
wishlist instead of minor. Feel free to change it.

>
> on my machine, I can get it up to about 9% CPU usage by this test...
>

With C, POSIX or an invalid locale:

  env LC_ALL=C dialog --menu text 0 0 0 $(seq 1 1000)

I get only about 15-20% CPU usage on my Athlon 600 MHz and the scrolling
is fast. But if I select a valid locale from the "locale -a" output:

  env LC_ALL=finnish dialog --menu text 0 0 0 $(seq 1 1000)

the scrolling is very slow and the CPU usage is 100%. If I increase the
menu items:

  env LC_ALL=C dialog --menu text 0 0 0 $(seq 1 10000)

The performance is bad also with the C locale and the startup time is
long.

My dialog is linked with libncursesw so that the USE_WIDE_CURSES gets
defined.

-- 
Lasse Kantola -- Lasse.Kantola@iki.fi -- http://www.iki.fi/Lasse.Kantola/



Message sent on to Lasse Kantola <Lasse.Kantola@iki.fi>:
Bug#294853. Full text and rfc822 format available.

Message #16 received at 294853-submitter@bugs.debian.org (full text, mbox):

From: Thomas Dickey <dickey@his.com>
To: 294853-submitter@bugs.debian.org
Subject: Re: Bug#294853: dialog: Bad performance with large menus.
Date: Sun, 13 Feb 2005 06:54:18 -0500 (EST)
On Sun, 13 Feb 2005, Lasse Kantola wrote:

> On Sat, 12 Feb 2005 17:49:49 -0500 Thomas Dickey <dickey@radix.net> wrote:
>>
>> I hadn't noticed (sorry).  Though I was aware that it could be a
>> problem, it hadn't become an issue til now.
>>
>
> In my use case, I use dialog to select one line out of about 1000 lines. I
> think that dialog was never meant to handle so big menus, but it would be
> of course very nice if the performance was independent of the size of the
> menu. Now that I think of it, I could have as well set the bug severity to
> wishlist instead of minor. Feel free to change it.

minor's ok.  I'll probably work on this in about a week (am in progress on
some other code).  It might be as simple as associating each line of the
list with a separate cache entry (some juggling, but no rewrite).

> the scrolling is very slow and the CPU usage is 100%. If I increase the
> menu items:
>
>  env LC_ALL=C dialog --menu text 0 0 0 $(seq 1 10000)

The practical limit, by the way, is 32767 (curses/ncurses store dimensions 
in a short, and it's likely that sign-extension issues prevent use past
that).

It's possible there are other scenarios where performance is poor. I 
hadn't considered this one - the caching was as I noted for input editing, 
where the length of the line was the consideration rather than the number 
of lines.

-- 
Thomas E. Dickey
http://invisible-island.net
ftp://invisible-island.net



Reply sent to Santiago Vila <sanvila@unex.es>:
You have marked Bug as forwarded. Full text and rfc822 format available.

Message #19 received at 294853-forwarded@bugs.debian.org (full text, mbox):

From: Santiago Vila <sanvila@unex.es>
To: Thomas Dickey <dickey@his.com>
Cc: 294853-forwarded@bugs.debian.org, Lasse Kantola <Lasse.Kantola@iki.fi>
Subject: Bug#294853: dialog: Bad performance with large menus. (fwd)
Date: Thu, 28 Apr 2005 20:23:21 +0200 (CEST)
Hi.

Received this from the Deibna bug system.

---------- Forwarded message ----------
From: Lasse Kantola <Lasse.Kantola@iki.fi>
To: Debian Bug Tracking System <submit@bugs.debian.org>
Date: Sat, 12 Feb 2005 00:07:49 +0200
Subject: Bug#294853: dialog: Bad performance with large menus.

Package: dialog
Version: 1.0-20050206-1
Severity: minor


To reproduce the problem set LC_ALL to some locale (not C or POSIX)
and execute:
  
    dialog --menu text 0 0 0 $(seq 1 1000)

Scroll down by pressing the down arrow key. The scrolling is
extremely slow and consumes a lot of CPU. Increase the "1000"
in the command to see the effect better.

It seems that the cache_list in the inputstr.c module scales
very badly. Below is a part of the gprof output:


Each sample counts as 0.01 seconds.
  %   cumulative   self              self     total           
 time   seconds   seconds    calls   s/call   s/call  name    
 51.35    126.42   126.42    45341     0.00     0.00  load_cache
 48.37    245.49   119.07    45341     0.00     0.00  save_cache


-- System Information:
Debian Release: 3.1
  APT prefers unstable
  APT policy: (500, 'unstable')
Architecture: i386 (i686)
Kernel: Linux 2.6.9
Locale: LANG=C, LC_CTYPE=fi_FI.UTF-8 (charmap=UTF-8)

Versions of packages dialog depends on:
ii  debianutils                 2.11.2       Miscellaneous utilities specific t
ii  libc6                       2.3.2.ds1-20 GNU C Library: Shared libraries an
ii  libncursesw5                5.4-4        Shared libraries for terminal hand

-- no debconf information



Message #20 received at 294853-forwarded@bugs.debian.org (full text, mbox):

From: Thomas Dickey <dickey@his.com>
To: Santiago Vila <sanvila@unex.es>
Cc: 294853-forwarded@bugs.debian.org, Lasse Kantola <Lasse.Kantola@iki.fi>
Subject: Re: Bug#294853: dialog: Bad performance with large menus. (fwd)
Date: Thu, 28 Apr 2005 15:17:05 -0400 (EDT)
On Thu, 28 Apr 2005, Santiago Vila wrote:

> Hi.
>
> Received this from the Deibna bug system.

yes, I spent some time on this, but have been dealing with bigger bugs in 
xterm and lynx (haven't forgotten this though).

-- 
Thomas E. Dickey
http://invisible-island.net
ftp://invisible-island.net



Message sent on to Lasse Kantola <Lasse.Kantola@iki.fi>:
Bug#294853. Full text and rfc822 format available.

Message #23 received at 294853-submitter@bugs.debian.org (full text, mbox):

From: Thomas Dickey <dickey@his.com>
To: 294853-submitter@bugs.debian.org
Subject: re: #294853: Bad performance with large menus.
Date: Sun, 30 Oct 2005 16:19:05 -0500
[Message part 1 (text/plain, inline)]
dialog 1.0-20051030 snapshot addresses this (it reduces the CPU load on
my machine from about 6.5% down to 2%).

-- 
Thomas E. Dickey <dickey@invisible-island.net>
http://invisible-island.net
ftp://invisible-island.net
[signature.asc (application/pgp-signature, inline)]

Reply sent to Santiago Vila <sanvila@debian.org>:
You have taken responsibility. Full text and rfc822 format available.

Notification sent to Lasse Kantola <Lasse.Kantola@iki.fi>:
Bug acknowledged by developer. Full text and rfc822 format available.

Message #28 received at 294853-close@bugs.debian.org (full text, mbox):

From: Santiago Vila <sanvila@debian.org>
To: 294853-close@bugs.debian.org
Subject: Bug#294853: fixed in dialog 1.0-20051107-1
Date: Tue, 08 Nov 2005 10:32:07 -0800
Source: dialog
Source-Version: 1.0-20051107-1

We believe that the bug you reported is fixed in the latest version of
dialog, which is due to be installed in the Debian FTP archive:

dialog_1.0-20051107-1.diff.gz
  to pool/main/d/dialog/dialog_1.0-20051107-1.diff.gz
dialog_1.0-20051107-1.dsc
  to pool/main/d/dialog/dialog_1.0-20051107-1.dsc
dialog_1.0-20051107-1_powerpc.deb
  to pool/main/d/dialog/dialog_1.0-20051107-1_powerpc.deb
dialog_1.0-20051107.orig.tar.gz
  to pool/main/d/dialog/dialog_1.0-20051107.orig.tar.gz



A summary of the changes between this version and the previous one is
attached.

Thank you for reporting the bug, which will now be closed.  If you
have further comments please address them to 294853@bugs.debian.org,
and the maintainer will reopen the bug report if appropriate.

Debian distribution maintenance software
pp.
Santiago Vila <sanvila@debian.org> (supplier of updated dialog package)

(This message was generated automatically at their request; if you
believe that there is a problem with it please contact the archive
administrators by mailing ftpmaster@debian.org)


-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Format: 1.7
Date: Tue,  8 Nov 2005 19:08:34 +0100
Source: dialog
Binary: dialog
Architecture: source powerpc
Version: 1.0-20051107-1
Distribution: unstable
Urgency: low
Maintainer: Santiago Vila <sanvila@debian.org>
Changed-By: Santiago Vila <sanvila@debian.org>
Description: 
 dialog     - Displays user-friendly dialog boxes from shell scripts
Closes: 294853 336986
Changes: 
 dialog (1.0-20051107-1) unstable; urgency=low
 .
   * New upstream release.
   * Fixes a problem with dlg_add_result in libdialog (Closes: #336986).
   * The previous release improved performance with large menus, by using
     tsearch() instead of a linked-list search (Closes: #294853).
Files: 
 d717182bc8a5ff1f3bd68bfc530653db 593 misc optional dialog_1.0-20051107-1.dsc
 0c133cb4bd01cdb34984095b90a29b18 310704 misc optional dialog_1.0-20051107.orig.tar.gz
 9e42bcde9cc01380355fc210f5d16bf3 8123 misc optional dialog_1.0-20051107-1.diff.gz
 6f2fbf7a95c44e9899b8eddcd1340142 210084 misc optional dialog_1.0-20051107-1_powerpc.deb

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.1 (GNU/Linux)

iD8DBQFDcOpCd9Uuvj7yPNYRAhbcAJ9qOmtk0/cOcALgssYzEc8zHMizIQCgvMSA
nO+VAk0q2H0UPx7UZnnvjhY=
=GGbx
-----END PGP SIGNATURE-----




Bug archived. Request was from Debbugs Internal Request <owner@bugs.debian.org> to internal_control@bugs.debian.org. (Mon, 25 Jun 2007 20:55:24 GMT) Full text and rfc822 format available.

Send a report that this bug log contains spam.


Debian bug tracking system administrator <owner@bugs.debian.org>. Last modified: Sun Apr 20 04:08:01 2014; Machine Name: beach.debian.org

Debian Bug tracking system
Copyright (C) 1999 Darren O. Benham, 1997,2003 nCipher Corporation Ltd, 1994-97 Ian Jackson.