[3457] in linux-announce channel archive
Linux-Announce Digest #748
daemon@ATHENA.MIT.EDU (Digestifier)
Wed Mar 8 16:39:32 2000
Message-ID: <20000308211310.11933.qmail@senator-bedfellow.mit.edu>
From: Digestifier <Linux-Announce-Request@senator-bedfellow.mit.edu>
To: Linux-Announce@senator-bedfellow.mit.edu
Reply-To: Linux-Announce@senator-bedfellow.mit.edu
Date: Wed, 8 Mar 00 16:13:08 EST
Linux-Announce Digest #748, Volume #3 Wed, 8 Mar 00 16:13:08 EST
Contents:
treescan 0.6 - optimised search for files in a directory tree (Jamie Lokier)
GTL-0.3.3 - Graph Template Library (Marcus Raitner)
WWW: LinuxLinks.com launches Linux Metacrawler search service (Steve Emms)
Not so simple 3D Game Version 1.12 (Joerg Scheurich aka MUFTI)
WWW: Announcing Gimp-Savvy.com (Carey Bunks)
----------------------------------------------------------------------------
From: Jamie Lokier <jamie.lokier@cern.ch>
Subject: treescan 0.6 - optimised search for files in a directory tree
Date: Wed, 8 Mar 2000 22:30:05 GMT
=====BEGIN PGP SIGNED MESSAGE=====
Announcing Treescan version 0.6
``A Faster Find''
Jamie Lokier, 6th March 2000
Description
- -----------
Treescan finds all the files in a directory tree and prints their
names, using an optimised disk access strategy.
It is similar to `find -print'. The added feature is that Treescan
optimises the I/O in various ways. It is sometimes much faster than the
naive strategy used by `find'.
There is an option to prime the system cache with the inodes of all the
files found. This often makes a subsequent program (such as `squid',
`find', `du' etc.) run faster.
The latest source is at:
http://www.tantalophile.demon.co.uk/treescan/treescan-0.6.tar.gz
News
- ----
Changes in version 0.6:
- Many bugs fixed.
- `-stat' option actually works. It was broken in version 0.5.
- ldiff regex quoting made more robust.
- New command line option `-d_type' to show file type info for debugging.
- A Linux kernel patch that gives us directory entry type information.
- Much faster using Linux directory entry type support.
- Fixed detection of empty directories.
- Faster on DJGPP (not tested).
- Document describing some of the optimisations.
Portability
- -----------
Treescan uses GNU Autoconf for configuration, and should be portable to
many unix-like operating systems. It should work even with old
operating systems. I've tried to support anything that GNU Find would
run on.
If you find a system which Treescan doesn't compile on, but GNU Find
does, please report that as a bug.
Uses
- ----
+ Treescan is handy when you want a list of all the files in a directory
tree. It is sometimes much faster than `find'.
+ `treescan /var/spool/squid -stat' is a very good thing to have in your
Squid startup script, just before starting Squid. Total startup time
for me is 6.7 seconds instead of 2 minutes, the disk does not thrash
noisily, and the system doesn't chug for 2 minutes after booting.
+ Treescan can be used in your `updatedb' script if you use one.
+ Treescan is good to run just before `gendiff' on Linux source trees.
It makes `gendiff' run a lot faster.
Similar gains occur with `find' and `du' and so forth.
Caveats
- -------
- - File names are not output in the same order as `find' nor any other
sensible order. To get `find'-compatible behaviour, pipe the
output through `sort'. This will be addressed in future.
Efficiency
- ----------
On the computers I have (both running Linux), Treescan 0.6 is always
faster than GNU Find 4.1. Sometimes the difference is dramatic,
sometimes it's not but Treescan is always faster.
Efficiency on different filesystems
- -----------------------------------
Treescan's strategy is optimised for any filesystem that fits these
assumptions: Inode number = approximate position of inode on disk (or
it's stored in the directory entry), and for directories, inode number =
approximate position of directory on disk. Inodes may be stored
separately from data, but it isn't required.
The following filesystems suit the inode assumption. Ext2 and NFS are
verified by experiment; the rest from reading Linux filesystem
implementations. The directory assumption is not so reliable, but
assuming it doesn't seem to make anything worse:
- ext2fs (standard fs on Linux and Hurd)
- Some implementations of FAT, VFAT and UMSDOS.
- BFS (UnixWare).
- AFFS (Amiga).
- EFS (SGI CD-ROM filesystem).
- HPFS (OS/2, I think).
- Minix.
- Romfs (Linux).
- QNX4.
- SysV (System V, Coherent and Xenix).
- UFS (BSD and derivatives such as SunOS and NeXTstep).
- NFS: Linux user-space nfsd/unfsd serving any of the above
- NFS: Linux kernel-space knfsd serving any of the above
- NFS: Probably every other Unix implementation of NFS,
serving any of the above.
Theoretically some filesystems may perform badly with Treescan, because
the inode numbers are really just hash values. Note: the user-space NFS
server `unfsd' works well with treescan -- the served inode numbers
retain the original ordering properties well enough.
The inode-ordering strategy can be disabled using the `-nosort' flag.
In this case Treescan can still be faster than `find' because of other
things it does.
(The other things Treescan does are: fewer system calls, avoid directory
name lookups when possible, scan directory inodes in clusters, and avoid
calling stat() on non-directories or even reading the inodes from disk
if the operating system supports the right features. (Linux doesn't
really support d_type yet but I think BSD does). See the ALGORITHM file
for details).
There are older systems on which GNU Find may run faster, for the
moment: specifically those without the fchdir() system call. We don't
follow GNU Find's strategy on those systems. The problem will be
addressed in future.
The goal is to provide the same or better level of performance compared
with `find' on all platforms.
Efficiency on Linux
- -------------------
Some kernel patches are included that really speed up scanning. Apply
them, and also run `tune2fs -O filetype' on all your ext2 filesystems
using e2fsprogs-1.17 or later. (Don't forget to unmount the
filesystems, run tune2fs, then e2fsck -- see the tune2fs man page).
However, Treescan is faster than `find' on Linux even without the
patches and filesystem enhancements.
Why I wrote Treescan
- --------------------
I wrote Treescan to make the web cache Squid start faster. Every time
I booted my computer, Squid would start, and spend the next 2 minutes
thrashing the disk as hard as possible. It was accessing the disk in a
more or less random fashion.
Linux would crawl along for those 2 minutes, and my poor disk would make
the noise that suffering disks make for that time.
I prefer Linux to be lean and fast from the start :-)
I prefer my disk not to be worn out by unnecessary heavy activity :-)
Treescan solves this problem very well: 6 seconds instead of 2 minutes.
Another goal is to make `updatedb' faster. That is the only other
program which thrashes my disk heavily, and it does it every night.
Treescan is now always faster than `find' for this in my tests.
Now I've expanded the goal: to be as efficient as a good implementation
of `find' in all reasonable cases. And then to package it into a
library, because lots of programs want to list directories or get the
attributes of many files efficiently.
Work in progress
- ----------------
The scanning strategy still needs a bit of work for the large disk
cases. Specifically, what is best to do when the buffer cache and
dentry cache don't hold everything (Linux terminology)? Thoughts on
this are particularly appreciated.
I detect this by assuming "fd open == inode guaranteed in memory, fd
closed == not guaranteed, always enough buffer cache to hold directory
contents for search". In other words, things start going pear shaped
when I run out of open directory file descriptors and have to close
some. I consider that the closed inodes may get flushed from the inode
cache at any time after that.
The problem of which inodes to close when under pressure is a rather
interesting logic optimisation problem, because there are
interdependencies and unknowns.
More things are in the TODO list.
License
- -------
Treescan is copyrighted by me, and currently licensed under the GNU
General Public License (GPL). If it looks like becoming a useful
library, I will probably change it to the Lesser GPL (LGPL).
Final notes
-----------
It's not obvious what is the best strategy for handling the cases when
I've run out of file descriptors. Also I want to stimulate some
interest in this lest it turn into rusty old code while I'm busy with
other things. So I decided to release this version to get some
feedback. Please send me some!
If this program helps you to spot bottlenecks in your favourite free
kernel, so much the better!
Enjoy,
- -- Jamie Lokier
Jamie Lokier <jamie@imbolc.ucc.ie>
- --
This article has been digitally signed by the moderator, using PGP.
http://www.iki.fi/mjr/cola-public-key.asc has PGP key for validating signature.
Send submissions for comp.os.linux.announce to: linux-announce@news.ornl.gov
PLEASE remember a short description of the software and the LOCATION.
This group is archived at http://www.iki.fi/mjr/linux/cola.html
=====BEGIN PGP SIGNATURE=====
Version: 2.6.3i
Charset: latin1
iQCVAgUBOMbUbVrUI/eHXJZ5AQHnBwP/Sz27tEylUYT0Xzg82YCc5gFIbipzZ+M/
D1fuVMXntqJh5ExNljNTliKFDbrA0c6P7pO8PI+OE4Ar3mrMgkpuvm8vI56ADp38
+mIlCRkeW4mNiiUXEXQAM/ubDNjkYvDLF6AADc3+JR5wFC7c41WnVjpzsBsG80wI
aewf0G7a02A=
=MArV
=====END PGP SIGNATURE=====
------------------------------
From: Marcus Raitner <raitner@infosun.fmi.uni-passau.de>
Subject: GTL-0.3.3 - Graph Template Library
Date: Wed, 8 Mar 2000 22:31:29 GMT
=====BEGIN PGP SIGNED MESSAGE=====
- -----BEGIN PGP SIGNED MESSAGE-----
The Graph Template Library - GTL
Release 0.3.3
WHAT IS GTL?
====================
Since we are intensively working with graph algorithms
especially in Graphlet (http://www.fmi.uni-passau.de/Graphlet/),
we decided to implement GTL, a graph library based on STL. For
the design of GTL's API the API of LEDA has served as a basis.
GTL contains the classes needed to work with graphs, nodes and
edges and some basic algorithms as building blocks for more
complex graph algorithms. Further algorithms are under work.
CHANGES AND FIXES (since 0.3.2):
=======================================
* Now really contains Visual C++ project files
* Added two partitioning algorithms implemented by Christian
Bachmaier <bachmaie@fmi.uni-passau.de>.
* Added algorithm for connected components
* Added methods to change the source or target of an edge.
* Some more assertions added. Mostly to check if the
arguments to new_edge, del_edge, etc. are really
elements of the graph.
FEATURES:
=================
* Datastructures for handling graphs efficiently.
* Designed to be extended to fit your own needs.
* Basic (extensible) graph algorithms:
- Depth First Search (DFS)
- Breadth First Search (BFS)
- Topological Sorting
- Biconnectivity Test
- Connected Components
- ST-Numbering
- Maximum-Flow
- Partitioning
* Planarity Test with planar embedding and detection of
subgraph homeomorphic either to K5 or ot K3,3 in case
graph is not planar. The test is an implementation of the
Booth and Luecker version of the Lempel, Even, Cederbaum
algorithm. If the graph is planar, the test takes O(n) time
if n is the number of nodes. Tests show that on a Sun Sparc
Ultra 10 it takes approx. 1.3 sec to test a planar graph
with 10000 nodes.
* GML file format support
(see http://infosun.fmi.uni-passau.de/Graphlet/)
Please refer to our homepage for details.
AVAILABILITY:
=====================
We are currently using GTL in Graphlet on the following
platforms:
* Solaris with egcs-1.0.3 or later.
* Linux with egcs-1.0.3 or later.
* MS Windows NT/95/98 and Visaul C++ 5.0 Service Pack 3
* MS Windows NT/95/98 using Visual C++ 6.0 Service Pack 3
The following configurations are reported to work:
* HP-UX 9.07 with gcc-2.8.1
* Free-BSD 4.0 with gcc-2.95.2
The latest version is GTL-0.3.3.
The source code can be downloaded from:
http://infosun.fmi.uni-passau.de/GTL/archive/
HOMEPAGE:
=================
The GTL WWW homepage is
http://infosun.fmi.uni-passau.de/GTL/
- -----BEGIN PGP SIGNATURE-----
Version: 2.6.3ia
Charset: noconv
Comment: Processed by Mailcrypt 3.5.3, an Emacs/PGP interface
iQCVAwUBOMTclBSzPv2Rql0pAQErgwP9Heae6lDN5Vdy7A/tz3r1iriEitfn20TW
u7XKUM0i8BPckI8tqT97QzP33Wq4JerW7x9YPXEG8tnc36lXnqVPj9qIW4UKuZdY
vPf8NglARbil2KJyFtke163TDffL9MlKiuGVooEH1OSO3+XygGE5Q7ck1xvck3D6
Q+045y1gIb8=
=QY/6
- -----END PGP SIGNATURE-----
- --
This article has been digitally signed by the moderator, using PGP.
http://www.iki.fi/mjr/cola-public-key.asc has PGP key for validating signature.
Send submissions for comp.os.linux.announce to: linux-announce@news.ornl.gov
PLEASE remember a short description of the software and the LOCATION.
This group is archived at http://www.iki.fi/mjr/linux/cola.html
=====BEGIN PGP SIGNATURE=====
Version: 2.6.3i
Charset: latin1
iQCVAgUBOMbUwlrUI/eHXJZ5AQG30gP+JX/TsHCSsffaUVbyfB5ZA8LQxbHVgQsc
7TvIgk16L3kn/mKXuATqRzUV+sTU6SddYQ7OGNitQEwfLpgq6oGi2Uh/SP1DK6tH
PG55pDkYDhuNLG7UqOqtP38FzbQi7NuVQJ2W89mXbUPpXO6FbvbmCqAVkfIh4od+
eGnH8Y+UO6I=
=owGd
=====END PGP SIGNATURE=====
------------------------------
From: Steve Emms <sde@linuxlinks.com>
Subject: WWW: LinuxLinks.com launches Linux Metacrawler search service
Date: Wed, 8 Mar 2000 22:33:55 GMT
=====BEGIN PGP SIGNED MESSAGE=====
LinuxLinks.com is proud to announce a metacrawler service to complement
its existing search facilities.
The metacrawler allows you to search for linux related enquiries from
the following search engines: Aol, DirectHit, Excite, Lycos, Msn,
Netscape and Yahoo. In addition the web search facility allows you
to make specialised targeted searches from hundreds of dedicated sites.
For example a search in our Usenet category will target AltavistaNews,
Deja, Jumbo, RemarQ, ShareWare and TalkWay or a search in our MP3
section will target Astraweb, MP3, Mp3Lycos, OthNet, PlayDude & ToLook4.
The metacrawler service is available at http://web.firstlinux.net/
and will be incorporated into the FirstLinux search engines shortly.
Sites are not verified before inclusion in web crawler databases
(unlike LinuxLinks.com) so we cannot guarantee the quality of information
provided by the engine. This is the search to try if you cannot find what
you want in the LinuxLinks database.
Linux Metacrawler represents an addditional free service provided by the
Firstlinux.com network.
- --
Steve Emms MA
http://www.linuxlinks.com/
http://www.firstlinux.com/
- --
This article has been digitally signed by the moderator, using PGP.
http://www.iki.fi/mjr/cola-public-key.asc has PGP key for validating signature.
Send submissions for comp.os.linux.announce to: linux-announce@news.ornl.gov
PLEASE remember a short description of the software and the LOCATION.
This group is archived at http://www.iki.fi/mjr/linux/cola.html
=====BEGIN PGP SIGNATURE=====
Version: 2.6.3i
Charset: latin1
iQCVAgUBOMbVVFrUI/eHXJZ5AQHtWgP/QBNbO1qKuoaAc6dbttOR+giQkNetpFg6
Nv99nBJVwFgbz8HP3xNTJZloNZ/EKl7DGn3/kNgECei1fe1rQ5jnTJZQ2jR7Y60B
o1ADknpQOqrWrYuVhZ2IiM5unNSqY+vc2u8NJ+9VeAwnI/zsqGZ0OBkR403mbGKS
aEd4bxaMI7Y=
=eQhy
=====END PGP SIGNATURE=====
------------------------------
From: Joerg Scheurich aka MUFTI <Joerg.Scheurich@RUS.Uni-Stuttgart.DE>
Subject: Not so simple 3D Game Version 1.12
Date: Wed, 8 Mar 2000 22:32:58 GMT
=====BEGIN PGP SIGNED MESSAGE=====
Announcing new release version of:
"Not so Simple 3D game" written in VRML (Virtual Reality Modelling Language)
Based on a VRML features demo by ICA University Stuttgart and
programs by Brian Wellington/Matias Duarte and Steve Baker (all Freeware)
Modifications, additional design and programming by J. Scheurich (AKA MUFTI)
mufti@csv.ica.uni-stuttgart.de
This game still lacks a name and a good story, but i am working on this.
Despite this, the current version 1.12 is usable as a practise mode.
Task:
You have to steer a warbird and you have to catch the enemy cubes.
Drag the background with the pointer to steer the warbird.
You can also spit to the cube by releasing the pointer button.
Installation:
To use, you need a VRML Browser. I recommend lookat as Linux VRML browser.
vrwave 0.9 lacks the script node and freewrl crash for a unknown reason.
Under other OS, i recommend cosmoplayer as VRML browser.
Sourcecode of lookat: http://www.openvrml.org/modules/libvrml97.html
You can test the program via the www (about 100KB) with
lookat http://www.csv.ica.uni-stuttgart.de/homes/js/vrmldemo/warbird.wrl
You can download the program in whole (about 100KB) by HTTP from
http://www.csv.ica.uni-stuttgart.de/homes/js/vrmldemo/warbird.tgz
this include 3D Models and possible modifications tailed for faster
3D Hardware.
3D Hardware:
Without 3D hardware this program should work good enough with a Intel
Pentiuum II/MMX 266 Mhz. The game is playable with a Voodo 1/2 card
in full screen mode (without seeing the pointer) by selecting
a 800x600 Mode of the X-Server and running with the options
"lookat -geometry 800x600 warbird.wrl". You better do not use a
windowmanager in this mode....
Copyright:
GPL
All opinions expressed in this program are strictly by
J. Scheurich (AKA MUFTI) and have nothing to do with the opinions of
University Stuttgart oder its Institute of Computer Applications.
Details:
http://www.csv.ica.uni-stuttgart.de/homes/js/vrmldemo/README
- --
This article has been digitally signed by the moderator, using PGP.
http://www.iki.fi/mjr/cola-public-key.asc has PGP key for validating signature.
Send submissions for comp.os.linux.announce to: linux-announce@news.ornl.gov
PLEASE remember a short description of the software and the LOCATION.
This group is archived at http://www.iki.fi/mjr/linux/cola.html
=====BEGIN PGP SIGNATURE=====
Version: 2.6.3i
Charset: latin1
iQCVAgUBOMbVGlrUI/eHXJZ5AQEWqgP/Tasm0Nc2JwchH2wZ8+SCUpidHClL3kfV
B+o5rPukXv1AlSL8nLrQYxqmRjuELzm9x74zUNpuxHwK3cqDLRxZFAo21RtpBAua
87JNtdMFbilG2kZNcVOQPcJoWaS7jTpjO2dFm5h0P/mv+AkzTWVIWKZCuirOTY/2
keCFPDRcuvM=
=0exi
=====END PGP SIGNATURE=====
------------------------------
From: Carey Bunks <cbunks@gimp-savvy.com>
Subject: WWW: Announcing Gimp-Savvy.com
Date: Wed, 8 Mar 2000 22:38:10 GMT
=====BEGIN PGP SIGNED MESSAGE=====
===== Announcing =====
Gimp-Savvy.com
http://gimp-savvy.com/
What is it?
- -----------
Gimp-Savvy.com is a web site providing high-level educational
and practical resources for the Gnu Image Manipulation Program,
a.k.a. the GIMP, and seeking to promote its skillful and
knowledgeable use.
On Site Resources
- -----------------
The primary resource provided by Gimp-Savvy.com is an intermediate
to advanced guide entitled "Grokking the GIMP", which is available
in its entirety on this web site under an open publication license.
"Grokking the GIMP" covers the use of the GIMP's core tools,
explaining methods for performing operations with layers,
selections, and masks. The basic concepts of colorspaces and their
uses in image editing are developed in detail, and in-depth
instruction is given on the best ways to perform high-level tasks
such as color correction, photo touchup, image enhancement, collage,
and photo montage.
In addition to its conceptual approach to image manipulation,
"Grokking the GIMP" also presents nine major projects. These
illustrate how the GIMP's tools are used to accomplish more
sophisticated image editing tasks and give a clearer picture of
how tools interact and are used together.
To Visit Gimp-Savvy.com
- -----------------------
http://gimp-savvy.com/
Carey Bunks
cbunks@gimp-savvy.com
- --
This article has been digitally signed by the moderator, using PGP.
http://www.iki.fi/mjr/cola-public-key.asc has PGP key for validating signature.
Send submissions for comp.os.linux.announce to: linux-announce@news.ornl.gov
PLEASE remember a short description of the software and the LOCATION.
This group is archived at http://www.iki.fi/mjr/linux/cola.html
=====BEGIN PGP SIGNATURE=====
Version: 2.6.3i
Charset: latin1
iQCVAgUBOMbWUlrUI/eHXJZ5AQEXAQP9G5xNZx+8LqCLVNnkcb1S+fp7YuqYSLw9
466YOQ9h+FBrSKQRD7nTbud9L2FNDW4cBU3hTzHQvd/8z8m2yH1p+hWTCpcS26jy
UWd4iyB+X8xh0Qr8VXTf/7Wlx4EZwRcZ8ERXe7bmR2MQheml3DnYWQcjC0ez/OGW
6UDqaPOz+fE=
=j0OE
=====END PGP SIGNATURE=====
------------------------------
** FOR YOUR REFERENCE **
The service address, to which questions about the list itself and requests
to be added to or deleted from it should be directed, is:
Internet: Linux-Announce-Request@NEWS-DIGESTS.MIT.EDU
You can submit announcements to be moderated via:
Internet: linux-announce@NEWS.ORNL.GOV
Linux may be obtained via one of these FTP sites:
ftp.funet.fi pub/Linux
tsx-11.mit.edu pub/linux
sunsite.unc.edu pub/Linux
End of Linux-Announce Digest
******************************
