bug#13127: [PATCH] cut: use only one data strucutre

[Cojocaru Alexandru]

On Sun, 09 Dec 2012 21:45:03 +0100
Jim Meyering  wrote:

> Thanks for the patch.
> This is large enough that you'll have to file a copyright assignment.
> For details, see the "Copyright assignment" section in the file
> named HACKING.

Fine.


> Have you considered performance in the common case?
> I suspect that a byte or field number larger than 1000 is
> not common.  That is why, in the FIXME comment above,
> I suggested to use an adaptive approach.  I had the feeling
> (don't remember if I profiled it) that testing a bit per
> input field would be more efficient than an in-range test.

Yes, it was the first thing I checked. And there's no performance loss.


> If you construct test cases and gather timing data, please do so
> in a reproducible manner and include details when you report back,
> so we can compare on different types of systems.

Here are my benchmarks:

OS:   Parabola GNU/linux-libre (linux-libre v3.6.8-1)
Compiler: GCC 4.7.2
Cflags:   -O2
LANG: C
CPU:  Intel Core Duo  (1.86 GHz) (L1 Cache 64KiB) (L2 Cache 2MiB)
Main memory:
 - Bank 0: DIMM DRAM Synchronous (1GiB) (width 64 bits)
 - Bank 1: DIMM DRAM Synchronous (1GiB) (width 64 bits)

NOTE: information gathered with `lshw'.


Summary (see the attached file for complete data):

### small ranges
cut-pre: 0:01.84
cut-post: 0:01.36
cut-split: 0:01.25

### bigger ranges
cut-pre: 0:11.74
cut-post: 0:09.20
cut-split: 0:07.91 ***

### fields
cut-pre: 0:02.90
cut-post: 0:02.68
cut-split: 0:02.85

### --output-delimiter
cut-pre: 0:02.90
cut-post: 0:02.74
cut-split: 0:02.80


NOTES:
 cut-pre is the current implementation and was compiled from commit ec48beadf.
 cut-post was compiled after applying the above patch to commit ec48beadf.
 cut-split was compiled after applying the `split-print_kth' patch to commit 
ec48beadf.


The main advantages cames from splitting `print_kth' into two
separate functions, so now `print_kth' does fewer checks.


Best regards,
Cojocaru Alexandru
OS:   Parabola GNU/linux-libre (linux-libre v3.6.8-1)
Compiler: GCC 4.7.2
Cflags:   -O2
LANG: C
CPU:  Intel Core Duo  (1.86 GHz) (L1 64KiB) (L2 2MiB)
Main memory:
 - Bank 0: DIMM DRAM Synchronous (1GiB) (width 64 bits)
 - Bank 1: DIMM DRAM Synchronous (1GiB) (width 64 bits)

NOTE: information gathered with `lshw'.


bash$ ./cut-pre 2> /dev/null # try not to count caching of shared libraries

### small ranges
bash$ for i in `seq 1 100`; do echo "abcdfeg" >> big-file; done

bash$ for i in 1 2 3; do /usr/bin/time ./cut-pre -b1,3 big-file > /dev/null; 
echo ; done
1.72user 0.11system 0:01.84elapsed 99%CPU (0avgtext+0avgdata 568maxresident)k
0inputs+0outputs (0major+168minor)pagefaults 0swaps

1.75user 0.08system 0:01.84elapsed 99%CPU (0avgtext+0avgdata 572maxresident)k
0inputs+0outputs (0major+168minor)pagefaults 0swaps

1.76user 0.07system 0:01.84elapsed 99%CPU (0avgtext+0avgdata 568maxresident)k
0inputs+0outputs (0major+167minor)pagefaults 0swaps


bash$ for i in 1 2 3; do /usr/bin/time ./cut-post -b1,3 big-file > /dev/null; 
echo; done
1.23user 0.12system 0:01.36elapsed 99%CPU (0avgtext+0avgdata 560maxresident)k
0inputs+0outputs (0major+165minor)pagefaults 0swaps

1.25user 0.09system 0:01.36elapsed 99%CPU (0avgtext+0avgdata 560maxresident)k
0inputs+0outputs (0major+165minor)pagefaults 0swaps

1.25user 0.09system 0:01.36elapsed 99%CPU (0avgtext+0avgdata 556maxresident)k
0inputs+0outputs (0major+164minor)pagefaults 0swaps


bash$ for i in 1 2 3; do /usr/bin/time ./cut-split -b1,3 big-file > /dev/null; 
echo ; done
1.15user 0.09system 0:01.25elapsed 99%CPU (0avgtext+0avgdata 572maxresident)k
0inputs+0outputs (0major+168minor)pagefaults 0swaps

1.15user 0.08system 0:01.25elapsed 99%CPU (0avgtext+0avgdata 568maxresident)k
0inputs+0outputs (0major+167minor)pagefaults 0swaps

1.14user 0.10system 0:01.25elapsed 99%CPU (0avgtext+0avgdata 568maxresident)k
0inputs+0outputs (0major+167minor)pagefaults 0swaps


### bigger ranges
bash$ yes $(for i in $(seq 1 10); do echo -n a; done) | dd of=big-lines 
ibs=11 count=1 iflag=fullblock

bash$ for i in 1 2 3; do /usr/bin/time ./cut-pre -b50-100,101-105, 
big-lines > /dev/null; echo; done
11.01user 0.70system 0:11.74elapsed 99%CPU (0avgtext+0avgdata 572maxresident)k
0inputs+0outputs (0major+168minor)pagefaults 0swaps

11.02user 0.70system 0:11.74elapsed 99%CPU (0avgtext+0avgdata 576maxresident)k
0inputs+0outputs (0major+169minor)pagefaults 0swaps

11.04user 0.66system 0:11.73elapsed 99%CPU (0avgtext+0avgdata 572maxresident)k
0inputs+0outputs (0major+168minor)pagefaults 0swaps


bash$ for i in 1 2 3; do /usr/bin/time ./cut-post -b50-100,101-105, 
big-lines > /dev/null; echo; done
8.65user 0.52system 0:09.20elapsed 99%CPU (0avgtext+0avgdata 560maxresident)k
0inputs+0outputs (0major+165minor)pagefaults 0swaps

8.59user 0.58system 0:09.20elapsed 99%CPU (0avgtext+0avgdata 556maxresident)k
0inputs+0outputs (0major+164minor)pagefaults 0swaps

8.53user 0.65system 0:09.21elapsed 99%CPU (0avgtext+0avgdata 560m

bug#13144: "comm" bug or strange behaviour

[Bob Proulx]

Matteo Zambelli wrote:
> Hi, i was trying to find common lines between the two attached
> files(both created with "dpkg --get-selections > filename.txt") with
> this command:
> 
> comm -12 squeeze-xfce-installed_packages.txt 
> squeeze-xfce-installed_packages.txt > result.txt
> 
> then i noticed that the line:
> 
> libcdio10   install
> 
> that is regularly present in both files, doesn't appear in the
> result(as well as few other lines).

Thank you for the report.  Also thank you for including the data sets
needed to reproduce the activity.  That's great.

Unfortunately I cannot reproduce your result.

  $ comm -12 squeeze-xfce-installed_packages.txt 
squeeze-xfce-installed_packages.txt | grep libcdio10
  libcdio10 install

And so there it is in the output??

> I have tried with option "--nocheck-order" and such, but those common
> lines are still missing in the output file.

Try 'sort -c' to check the sort ordering of both files.  (Looked okay
to me but it is locale dependent.)

What is your 'locale' setting?  (Affects sort order.)

  $ locale

In this case it shouldn't matter but what version of comm are you
using?  I know you reported your kernel version but that isn't really
associated.  (Think Squeeze with Backports.)

  $ comm --version

Verify that the 'comm' binary that you are running is the expected
one:

  $ type comm
  comm is hashed (/usr/bin/comm)

Bob