Faster conflict detection

TAAPArthur commented 2 years ago

Replace the use of grep to determine the unique dependencies with sort/comm.

While testing this discovered that a bug when generating the list of conflicts. If we had a list like "A B C", where B is the current package, we'd search " A B C " for " B " and replace it with "" so we'd end up with " AC " which is incorrect. That code has been modified to replace with " " such that we'd keep A and C separate.

dylanaraps commented 2 years ago

This does not work for me when installing for example bmake (conflict with /usr/bin/make not detected).

dylanaraps commented 2 years ago

While testing this discovered that a bug when generating the list of conflicts. If we had a list like "A B C", where B is the current package, we'd search " A B C " for " B " and replace it with "" so we'd end up with " AC " which is incorrect. That code has been modified to replace with " " such that we'd keep A and C separate.

~~When does this issue occur specifically? When there are spaces in paths?~~

I understand.

TAAPArthur commented 2 years ago

This does not work for me when installing for example bmake (conflict with /usr/bin/make not detected).

This should be resolved.

So I think I found 2 bugs. Not sure if they how they are related to this PR. I was install dash and bash and verifying /usr/bin/sh was a conflict. Eventually kiss i dash would yield

cp: /tmp/kiss/1808/extract/dash/usr/bin/sh -> /usr/bin/./sh: same file

And then if I forced removed dash and manually put something in /usr/bin/sh,

/usr/bin/kiss: line 164: cd: /var/db/kiss/installed/dash:

Which looks to relate to resolve_path and not being able to restore the old directory. If I can reproduce with vanilla master I'll open a dedicate issue/PR. Marking this PR as a draft for now since I don't have proof I didn't cause this.

dylanaraps commented 2 years ago

I can't reproduce your issue with master. Could be wrong though.

TAAPArthur commented 2 years ago

So ran through this with a couple of shells and verified the /usr/bin/sh conflict is still detected correctly.

dylanaraps commented 2 years ago

Will test your changes shortly, thanks.

dylanaraps commented 2 years ago

I am a little torn on this one. While it improves execution time for busybox grep it regresses execution times for all other grep implementations (when number of files is < 3000-4000). Interestingly, when number of files is increased this PR has a better execution time for all greps except for GNU's.

Tests of master

Below numbers are using kiss master (without your PR) to show difference in execution time between grep implementations (and just how slow busybox grep is). I have picked three packages to test against, bmake, util-linux and python.

The first two packages have conflicts (1 and many respectively). The third package has no conflicts on my system but many files (4000+).

Busybox grep

-> time kiss i bmake
Using ssu (to become root)
-> bmake Checking if manifest valid
-> bmake Checking if package installable
-> bmake Checking for package conflicts
Found conflict /usr/bin/make
-> bmake Converted all conflicts to choices (kiss a)
-> bmake Generating manifest
-> bmake Installing package (bmake@20210808-1.tar.zst)
-> bmake Installed successfully
real 0m 0.90s
user 0m 0.87s
sys 0m 0.03s

-> time kiss i util-linux
-> util-linux Checking if manifest valid
-> util-linux Checking if package installable
-> util-linux Checking for package conflicts
# ...
-> util-linux Converted all conflicts to choices (kiss a)
-> util-linux Generating manifest
-> util-linux Installing package (util-linux@2.37.2-1.tar.zst)
-> util-linux Installed successfully
real 0m 2.51s
user 0m 2.42s
sys 0m 0.10s

-> time kiss i python
Using ssu (to become root)
-> python Checking if manifest valid
-> python Checking if package installable
-> python Checking for package conflicts
-> python Installing package (python@3.10.0-1.tar.zst)
-> python Installed successfully
real 0m 25.57s
user 0m 24.36s
sys 0m 1.36s

GNU grep

-> time kiss i bmake
Using ssu (to become root)
-> bmake Checking if manifest valid
-> bmake Checking if package installable
-> bmake Checking for package conflicts
Found conflict /usr/bin/make
-> bmake Converted all conflicts to choices (kiss a)
-> bmake Generating manifest
-> bmake Installing package (bmake@20210808-1.tar.zst)
-> bmake Installed successfully
real 0m 0.09s
user 0m 0.08s
sys 0m 0.01s

-> time kiss i util-linux
-> util-linux Checking if manifest valid
-> util-linux Checking if package installable
-> util-linux Checking for package conflicts
# ...
-> util-linux Converted all conflicts to choices (kiss a)
-> util-linux Generating manifest
-> util-linux Installing package (util-linux@2.37.2-1.tar.zst)
-> util-linux Installed successfully
real 0m 0.31s
user 0m 0.22s
sys 0m 0.10s

-> time kiss i python
Using ssu (to become root)
-> python Checking if manifest valid
-> python Checking if package installable
-> python Checking for package conflicts
-> python Installing package (python@3.10.0-1.tar.zst)
-> python Installed successfully
real 0m 3.66s
user 0m 2.49s
sys 0m 1.37s

OpenBSD grep

-> time kiss i bmake
Using ssu (to become root)
-> bmake Checking if manifest valid
-> bmake Checking if package installable
-> bmake Checking for package conflicts
Found conflict /usr/bin/make
-> bmake Converted all conflicts to choices (kiss a)
-> bmake Generating manifest
-> bmake Installing package (bmake@20210808-1.tar.zst)
-> bmake Installed successfully
real 0m 0.21s
user 0m 0.18s
sys 0m 0.02s

-> time kiss i util-linux
-> util-linux Checking if manifest valid
-> util-linux Checking if package installable
-> util-linux Checking for package conflicts
# ...
-> util-linux Converted all conflicts to choices (kiss a)
-> util-linux Generating manifest
-> util-linux Installing package (util-linux@2.37.2-1.tar.zst)
-> util-linux Installed successfully
real 0m 0.71s
user 0m 0.62s
sys 0m 0.10s

-> time kiss i python
Using ssu (to become root)
-> python Checking if manifest valid
-> python Checking if package installable
-> python Checking for package conflicts
-> python Installing package (python@3.10.0-1.tar.zst)
-> python Installed successfully
real 0m 5.31s
user 0m 4.16s
sys 0m 1.37s

Toybox grep

-> time kiss i bmake
Using ssu (to become root)
-> bmake Checking if manifest valid
-> bmake Checking if package installable
-> bmake Checking for package conflicts
Found conflict /usr/bin/make
-> bmake Converted all conflicts to choices (kiss a)
-> bmake Generating manifest
-> bmake Installing package (bmake@20210808-1.tar.zst)
-> bmake Installed successfully
real 0m 0.14s
user 0m 0.11s
sys 0m 0.03s

-> time kiss i util-linux
-> util-linux Checking if manifest valid
-> util-linux Checking if package installable
-> util-linux Checking for package conflicts
# ...
-> util-linux Converted all conflicts to choices (kiss a)
-> util-linux Generating manifest
-> util-linux Installing package (util-linux@2.37.2-1.tar.zst)
-> util-linux Installed successfully
real 0m 0.45s
user 0m 0.34s
sys 0m 0.11s

-> time kiss i python
Using ssu (to become root)
-> python Checking if manifest valid
-> python Checking if package installable
-> python Checking for package conflicts
-> python Installing package (python@3.10.0-1.tar.zst)
-> python Installed successfully
real 0m 5.30s
user 0m 4.18s
sys 0m 1.30s

Tests of this PR

Below numbers show the same implementations using this PR. Naturally, removal of grep usage results in more or less identical numbers across the board (except for the python test).

Busybox grep

-> time kiss i bmake
Using ssu (to become root)
-> bmake Checking if manifest valid
-> bmake Checking if package installable
-> bmake Checking for package conflicts
Found conflict /usr/bin/make
-> bmake Converted all conflicts to choices (kiss a)
-> bmake Generating manifest
-> bmake Installing package (bmake@20210808-1.tar.zst)
-> bmake Installed successfully
real 0m 0.27s
user 0m 0.32s
sys 0m 0.03s

-> time kiss i util-linux
-> util-linux Checking if manifest valid
-> util-linux Checking if package installable
-> util-linux Checking for package conflicts
# ...
-> util-linux Converted all conflicts to choices (kiss a)
-> util-linux Generating manifest
-> util-linux Installing package (util-linux@2.37.2-1.tar.zst)
-> util-linux Installed successfully
real 0m 0.49s
user 0m 0.50s
sys 0m 0.09s

-> time kiss i python
Using ssu (to become root)
-> python Checking if manifest valid
-> python Checking if package installable
-> python Checking for package conflicts
-> python Installing package (python@3.10.0-1.tar.zst)
-> python Installed successfully
real 0m 6.37s
user 0m 5.30s
sys 0m 1.35s

GNU grep

-> time kiss i bmake
Using ssu (to become root)
-> bmake Checking if manifest valid
-> bmake Checking if package installable
-> bmake Checking for package conflicts
Found conflict /usr/bin/make
-> bmake Converted all conflicts to choices (kiss a)
-> bmake Generating manifest
-> bmake Installing package (bmake@20210808-1.tar.zst)
-> bmake Installed successfully
real 0m 0.27s
user 0m 0.27s
sys 0m 0.08s

-> time kiss i util-linux
-> util-linux Checking if manifest valid
-> util-linux Checking if package installable
-> util-linux Checking for package conflicts
# ...
-> util-linux Converted all conflicts to choices (kiss a)
-> util-linux Generating manifest
-> util-linux Installing package (util-linux@2.37.2-1.tar.zst)
-> util-linux Installed successfully
real 0m 0.49s
user 0m 0.43s
sys 0m 0.15s

-> time kiss i python
Using ssu (to become root)
-> python Checking if manifest valid
-> python Checking if package installable
-> python Checking for package conflicts
-> python Installing package (python@3.10.0-1.tar.zst)
-> python Installed successfully
real 0m 3.80s
user 0m 2.72s
sys 0m 1.36s

OpenBSD grep

-> time kiss i bmake
Using ssu (to become root)
-> bmake Checking if manifest valid
-> bmake Checking if package installable
-> bmake Checking for package conflicts
Found conflict /usr/bin/make
-> bmake Converted all conflicts to choices (kiss a)
-> bmake Generating manifest
-> bmake Installing package (bmake@20210808-1.tar.zst)
-> bmake Installed successfully
real 0m 0.27s
user 0m 0.32s
sys 0m 0.02s

-> time kiss i util-linux
-> util-linux Checking if manifest valid
-> util-linux Checking if package installable
-> util-linux Checking for package conflicts
# ...
-> util-linux Converted all conflicts to choices (kiss a)
-> util-linux Generating manifest
-> util-linux Installing package (util-linux@2.37.2-1.tar.zst)
-> util-linux Installed successfully
real 0m 0.49s
user 0m 0.47s
sys 0m 0.11s

-> time kiss i python
Using ssu (to become root)
-> python Checking if manifest valid
-> python Checking if package installable
-> python Checking for package conflicts
-> python Installing package (python@3.10.0-1.tar.zst)
-> python Installed successfully
real 0m 4.02s
user 0m 2.80s
sys 0m 1.48s

Toybox grep

-> time kiss i bmake
Using ssu (to become root)
-> bmake Checking if manifest valid
-> bmake Checking if package installable
-> bmake Checking for package conflicts
Found conflict /usr/bin/make
-> bmake Converted all conflicts to choices (kiss a)
-> bmake Generating manifest
-> bmake Installing package (bmake@20210808-1.tar.zst)
-> bmake Installed successfully
real 0m 0.28s
user 0m 0.34s
sys 0m 0.03s

-> time kiss i util-linux
-> util-linux Checking if manifest valid
-> util-linux Checking if package installable
-> util-linux Checking for package conflicts
# ...
-> util-linux Converted all conflicts to choices (kiss a)
-> util-linux Generating manifest
-> util-linux Installing package (util-linux@2.37.2-1.tar.zst)
-> util-linux Installed successfully
real 0m 0.48s
user 0m 0.47s
sys 0m 0.11s

-> time kiss i python
Using ssu (to become root)
-> python Checking if manifest valid
-> python Checking if package installable
-> python Checking for package conflicts
-> python Installing package (python@3.10.0-1.tar.zst)
-> python Installed successfully
real 0m 4.05s
user 0m 2.99s
sys 0m 1.34s

kisslinux / kiss