Re: Understanding version 4 packs

["Marco Costalba" <mcostalba@gmail.com>]

On 3/26/07, Nicolas Pitre <nico@cam.org> wrote:
> On Mon, 26 Mar 2007, Marco Costalba wrote:
>
> > Experimenting with file names cache in qgit I have found a big saving
> > splitting the paths in base name and file name and indexing both:
> >
> > drivers\usb\host\ehci.h
> > drivers\usb\host\ehci-pci.c
> > drivers\usb\host\ohci-pci.c
> > kernel\sched.c
> >
> > became:
> >
> > dir names table
> >
> > 0 drivers\usb\host
> > 1 kernel
> >
> >
> > file name table
> >
> > 0 ehci.h
> > 1 ehci-pci.c
> > 2 ohci-pci.c
> >
> > In this way a big saving is achieved in case of directories deep in
> > the tree (long paths) and a lot of files.
>
> Sure, but if you also consider drivers/usb/Makefile and drivers/Kconfig
> for example then you start losing on space saving.

In your example you'd have:

drivers/usb/Makefile
drivers/Kconfig

became

dir names table
0 drivers
1 drivers/usb

file name table
0 Makefile
1 Kconfig

I fail to see wher's the losing on space saving. More, you probably
have many paths both under 'drivers' and 'drivers/usb' and for each
added path it would be possible to avoid to store the prefix ('driver'
or 'driver/usb').

To better clarify, OBJ_DICT_TREE data *currently* looks like:

+------------+-------+-------+-------+-------+----
| NR_ENTRIES | name1 | hash1 | name2 | hash2 | ...
+------------+-------+-------+-------+-------+----
  vint        2 bytes 4 bytes 2 bytes 4 bytes

where name1 is an index into the packfile's sole EXTOBJ_FILENAME_TABLE.

The possible improve is to define OBJ_DICT_TREE like

+------------+-------+-------+-------+-------+----
| NR_ENTRIES | dir1   | fiile1 | hash1| dir 2| fiile2|...
+------------+-------+-------+-------+-------+----
  vint        2 bytes 2 bytes 2 bytes 4 bytes

where dir1 is an index into a new EXTOBJ_DIRNAME_TABLE and file1 is an
index in a new  EXTOBJ_FILENAME_TABLE.


EXTOBJ_FILENAME_TABLE is defined as the currently (but much smaller in
size!!) and keeps only the file names, not the full paths, while
EXTOBJ_DIRNAME_TABLE is defined as EXTOBJ_FILENAME_TABLE but without
MODE field (associated to files only) and is used to store the dir
names.

Decopuling dir names from file names could improve saving space
because the length of proposed EXTOBJ_FILENAME_TABLE +
EXTOBJ_DIRNAME_TABLE < current EXTOBJ_FILENAME_TABLE.

  Marco

P.S: Of course now you'd save 2+2 bytes in OBJ_DICT_TREE instead of 2
for 'name' index.
To avoid this and keep the idea of decopuling dir and file names an
still use 2 bytes in OBJ_DICT_TREE a possible layout of
EXTOBJ_FILENAME_TABLE could be:


 +------------+------+-------+-----------------+---
-+----------------+-------+------+----------+
 | NR_ENTRIES | dirA  |  file name1 | ofs1| file name2 | ofs 2|dirB
|file name3 | ofs3 | ....
 +------------+------+-------+-----------------+----
+---------------+--------+------+----------+

Where ofs1 and ofs2 are 2-bytes values pointing to dirA, ofs3 points
to dirB and so on.

Where the tree layout of the above example is:

dirA \ file name1
dirA \ file name2
dirB \ file name3

With this approach you have both the saving in case of directories
with many files and still 2 bytes per 'name' index in OBJ_DICT_TREE
(that points to 'file name' field). This approach saves space as soon
as directory names are longer then 2 chars.