Speed improvements

[worldveil]

Speed improvements

[milahu]

timestretch filter is a "simple but effective" way, to speed up both hashing and matching.

for example ....

ffmpeg -i input.mp4 -map 0:a:0 -ac 1 -filter:a atempo=2.0 -c:a pcm_s16le output.wav

.... to make audio shorter by factor 2

timestretch aka downsampling for fingerprint.fingerprint

DOWNSAMPLING_FACTOR = 2
# downsampling
# decrease sample rate by factor N
N = int(DOWNSAMPLING_FACTOR)
if N > 1:
    a = channel_samples
    l = (len(a)//N)*N
    a = a[:l].reshape(-1, N)
    a = np.mean(a, axis=1)
    channel_samples = a

# todo: scale offset times

for better accuracy, you can do "two-stage testing",
with a "quick but dirty" first stage, and a "slow but strict" second stage.
[ the game of Greed and Love .... ]
this will make hashing slower, but matching faster.
the first stage will reduce the "search space" for the second stage.

another optimization path:
stop matching at the first "good match", and avoid scanning the rest of the haystack.
if this is not possible in one pipeline (depth first search, greedy processor, realtime FFT),
then divide the haystack and conquer step by step.
haystack?
we use dejavu for "audio pattern matching",
to find the offset / position of a few short audio clips in one long audio stream.

faster hash function for fingerprint.generate_hashes

import mmh3, binascii
import xxhash

k = str(freq1) +'|'+ str(freq2) +'|'+ str(t_delta)

#h = hashlib.sha1(k).hexdigest() # --> 40 hexs
h = binascii.hexlify(mmh3.hash_bytes(k)) # --> 32 hexs
#h = xxhash.xxh64_hexdigest(k) # --> 16 hexs

yield (h[0:FINGERPRINT_REDUCTION], t1)

mmh3 is indeed faster than sha1. with xxhash, i get no matches

[zzzhe1990]

sorry for digging this old post out. I am now working on accelerating the training part, actually the fingerprinting. I got a big sample of about 300 songs. I noticed that mysql takes an extremely large of time that made me crazy. By typing "top", I can see that my multi-processing "python" task have done, but "mysql" task keeps running for hours (at around 40-50% cpu usage) as well as the master process of "python" at cpu usage of 4-7%. So, this is telling me that mysql is the bottleneck on fingerprinting for a large size of samples. Is that the same on your side? Do you have any experience of running test on large samples?

Thanks for any information.

[zzzhe1990]

Follow up. The problem I mentioned above might be caused by MySQL, but there is another possibility that something wrong with the multi-processes termination. In init.py, there is a code segment like:

`
while True:

        try:

            song_name, hashes, file_hash = iterator.next()

        except multiprocessing.TimeoutError:

            continue

        except StopIteration:

            break

        except:

            print("Failed fingerprinting")

            #Print traceback because we can't reraise it here       

            traceback.print_exc(file=sys.stdout)

        else:

            sid = self.db.insert_song(song_name, file_hash)

            self.db.insert_hashes(sid, hashes)

            self.db.set_song_fingerprinted(sid)

            self.get_fingerprinted_songs()

    pool.close()

    pool.join()`

Since I made changes to scipy ni_filter.c to enable multi-threading, which gives me a fly on fingerprinting, the situation now is that python runs multi-processing, and each process has multi-threads supported. I do not know if the support of multi-threading cause any troubles in the code above? Like the termination of some thread is not captured, so that the termination loop will never stop?

[artgancz]

Firstly

however I do not understand the binary_erosion part

If I understand it correctly the purpose of erosion was exactly to

reduce space complexity

by removing single peaks and reduce the groups of them. But I tested the project with a set of 150 songs and removing this part didn't affect the accuracy.
Secondly
You are completely right that adding new songs is extremely slow and the MySQL part is a problem here since InnoDB is not optimal choice when it comes to INSERT statements (but is really awesome with SELECT statements). Unfortunately I focused mostly on the speed of fingerprinting and searching in database, so if you are interested in this part of the project then I can give some more tips, but I really don't know how to speed up appending new songs to database. I guess that it requires some tuning in InnoDB settings (I can recommend here https://www.percona.com/blog/2016/05/03/best-practices-for-configuring-optimal-mysql-memory-usage/ and https://www.percona.com/blog/2016/10/12/mysql-5-7-performance-tuning-immediately-after-installation/) to force MySQL somehow to append the new records in parallel.

[mauricio-repetto]

Hello everyone, I've added a pr #205 with some modifications to the code, I could get down recognizing times from 20 seconds to ~3 seconds on songs of 3:30 minutes in average without hurting the accuracy. I've the same doubts of you regarding the erosion portion but I didn't want to discard it since does not take much time to process.
The pr is actually to migrate dejavu to python 3.6.6, solving a couple of bugs that I identified, adding support for mysql new connector and postgresql. There a couple of features more as well.. but please feel free to try it and let me know what do you think, thanks.

[worldveil]

Rather than waxing about particulars of the algorithm too much, I'd say that a test suite will certainly be the best way to start (looking forward to @pguridi PR for that?). A decently large corpus of audio from which to ensure the accuracy is maintained with speedups is necessary. In my mind, accuracy comes first. If people are speed manics they should be using echoprint anyway. But a test suite is a way to get numbers into the conversation rather than conjecture.

To wax a bit, the window size can't go much lower at least to my memory. The overlap ratio could be a good way to start. The real bottleneck is the peak finding (scipy.ndimage.filters) - a better way to do that will give you real gains. The easy way is to play with neighborhood size (smaller will go faster, but will have more lower quality peaks). The hard way is of course some sort of efficient local peak finding algorithm, probably a divide and conquer approach.

[worldveil]

Thinking about it a bit more, a really simple way to speed up the fingerprinting process might be to change the hash function. SHA-1 is probably overkill -- cryptographic guarantees on collisions aren't needed, and a different hash function like Murmur could be much faster.

That said, improving the peak finding by dropping into C with Cython is probably the biggest bite to take out of the time, but without profiling, that's just an educated guess.

I've spent my bandwidth for the time being adding a testing framework, but I'd certainly accept a PR on this topic.

[utilitarianexe]

So I have profiled the code. Peakfinding is with out a doubt the slowest part. Second slowest part is the sql for matching. The peakfinding is already done in C by scipy. And the C code part is the bottle neck. An impoved algorythem definityly seems possible here though.

[utilitarianexe]

Oh here is a example profile

Mon Dec 8 16:40:02 2014 profile

     35761738 function calls (35758992 primitive calls) in 467.473 seconds

Ordered by: cumulative time

ncalls tottime percall cumtime percall filename:lineno(function)
1 0.001 0.001 467.475 467.475 dejavu_match_library.py:1()
13 0.000 0.000 467.205 35.939 init.py:172(recognize)
13 0.002 0.000 467.204 35.939 recognize.py:51(recognize)
13 0.088 0.007 467.203 35.939 recognize.py:35(recognize_file)
13 0.131 0.010 456.447 35.111 recognize.py:14(_recognize)
26 0.893 0.034 455.465 17.518 init.py:114(find_matches)
26 11.347 0.436 363.659 13.987 fingerprint.py:64(fingerprint)
26 1.540 0.059 332.437 12.786 fingerprint.py:92(get_2D_peaks)
26 0.000 0.000 326.423 12.555 filters.py:931(maximum_filter)
26 0.001 0.000 326.423 12.555 filters.py:849(_min_or_max_filter)
26 326.410 12.554 326.410 12.554 {scipy.ndimage._nd_image.min_or_max_filter}
1356269 2.036 0.000 61.790 0.000 database_sql.py:280(return_matches)
1498 1.294 0.001 59.179 0.040 cursors.py:164(execute)
1498 0.007 0.000 53.627 0.036 cursors.py:353(_query)
1498 0.018 0.000 51.139 0.034 cursors.py:315(_do_query)
1500 50.108 0.033 50.108 0.033 {method 'query' of '_mysql.connection' objects}
1524852 11.372 0.000 29.122 0.000 fingerprint.py:133(generate_hashes)
26 0.000 0.000 19.875 0.764 mlab.py:429(specgram)
26 9.626 0.370 19.875 0.764 mlab.py:206(_spectral_helper)
4574478 3.923 0.000 15.199 0.000 numeric.py:1581(array_str)

[worldveil]

Could you post code/instructions to generate these profiles?

[utilitarianexe]

will do in a bit

[utilitarianexe]

python -m cProfile -o my_profile -s cumulative dejavu.py recognize file ~/repos/dejavu/mp3/some_long_song.mp3

import pstats
p = pstats.Stats('my_profile')
p.strip_dirs().sort_stats('cumulative').print_stats()

Also for the building library part there seem to be some weird things that make the accessing the db slow.

[Hoohaha]

I am also researching at the audio recognition. But it is big different with the part of fingerprints-extract. I think that the speed is the most point. With the numbers of songs increase in database, the time cost will be terrible, and the users would not tolerate this. Actually, the speed bottleneck is the progress of searching in the database. If we can find a new music index or a new way to compute the distance between two songs, the speed will be greatly improved.

[worldveil]

@Hoohaha fingerprinting or locally sensitive hashing in general does not produce distances between audio files. It merely creates derivative signals that are deterministic and noise-resistant.

[no-identd]

How about using the Constant-Q transform to speed this up?

See https://en.wikipedia.org/wiki/Constant-Q_transform#Fast_calculation_using_FFT

(for more related & interesting reading, see here, although I wouldn't expect speed improvements via that, it's certainly interesting:

• https://en.wikipedia.org/wiki/Morlet_wavelet
• https://en.wikipedia.org/wiki/List_of_Fourier-related_transforms
• https://en.wikipedia.org/wiki/Nyquist%E2%80%93Shannon_sampling_theorem#Nonuniform_sampling
• https://www.wired.com/2010/02/ff_algorithm/all/1
• http://nuit-blanche.blogspot.com/2010/03/why-compressed-sensing-is-not-csi.html
  )

[gudlucsam]

Hi @worldveil I tried implementing the fingerprinting in Cython as you suggested, but didn't get most improvement.... after implementing i profiled it and realized that execution time only reduced by about 1minute.
Also, since Scipy is already in C, there wasn't much improvement i could make on it, but only to statically type variables. Are there ideas of any algorithm for peak finding that you could suggest?
thank you.

[NathanielCustom]

The first parts go over my head without deeper explanation, so I can't comment.
The last part on "stop matching at the first "good match"" I want to explore...

What defines a "good match"? From my understanding Dejavu takes the sample and tries to find all the matches within each neighborhood slice for each song in the database. The more matches within the neighborhood the higher the returned "confidence" value.
I currently do this in a project where I will only accept results if the "confidence" is higher than a predetermined number, but AFTER the database has been searched. To apply this logic while the database is being searched is something I will have to look into, but I imagine that the value used to define a "good match" will depend on the project or type of audio fingerprinted.

[milahu]

stop matching at the first "good match"

What defines a "good match"?

let me rephrase to:
add support for "inter process communication" and "parallel processing",
to allow better control / flexibility / speed

the matching process should "yield" matches as soon as possible,
and continue to "yield" confidence values for the current match.

the controller process does observe the match/confidence data,
and when "satisfied" he can stop the matching process.
this is useful to speed up "single file matching".

.... or trigger a callback function,
like "print match to logfile"
or "cut stream from last match to current match"
or "mute commercial break" (audio adblocker) ....
and continue to observe the matching process.
this is useful to analyze "live streams"
or to observe "long streams" for different audio patterns
----> simple "machine hearing"

[artgancz]

There are two pretty easy tricks to speed up this project a little bit, first one: replace matplotlib.specgram inside fingerprint.py with scipy.signal.spectrogram (with detrend=False for compatibility). Second by tuning MySQL: https://www.percona.com/blog/2006/09/29/what-to-tune-in-mysql-server-after-installation/ and one more: from my experiments the part with binary_erosion is completely useless.

[omertoptas]

from my experiments the part with binary_erosion is completely useless.

Thank you for the hint , however I do not understand the binary_erosion part. It is supposed to reduce space complexity, right? Also which tunings do you suggest in the link you provided. I want to try this fingerprinting algorithm in a big data (around 2million songs) but first I want to get a reasonable results from a smaller sample like 1000songs. Currently there are 100 songs fingerprinted in MySql databases I created and the ammount of data stored in this database is about 1.3Gb.

[omertoptas]

So, this is telling me that mysql is the bottleneck on fingerprinting for a large size of samples. Is that the same on your side? Do you have any experience of running test on large samples?

Today I have done the testing with 100 songs (all of them about 3min or more long) , fingerprinting was done in minutes (with 8 cpu working almost at %100 all time) then when fingerprinting done, cpu usage drop to %10-%12 with only 1 or 2 cpu working. Then I started to watch phpmyadmin site to follow the state of database and I saw that songs are added to database 1 by 1 and very slowly. It took about 2 hours to complete the task.

After that I tried to fingerprint 30 songs from a music list I created and it took about 40 mins to complete the task and only in just first 2 mins fingerprinting was completed. Rest of the time spent while writing the data to MySQL database.

[omertoptas]

I guess that it requires some tuning in InnoDB settings (I can recommend here https://www.percona.com/blog/2016/05/03/best-practices-for-configuring-optimal-mysql-memory-usage/ and https://www.percona.com/blog/2016/10/12/mysql-5-7-performance-tuning-immediately-after-installation/) to force MySQL somehow to append the new records in parallel.

IT WORKED, thank you.
I have just completed a test, first I tried to fingerprint 30song files without tuning, it took 40 mins to complete, after that I created a new database and completed tuning, then fingerprinted the same 30song files and it took 10 mins to complete. I see this is an absolute win 😄 (I used the first 4 options mentioned in the second link you provided.)

[omertoptas]

Unfortunately I focused mostly on the speed of fingerprinting and searching in database, so if you are interested in this part of the project then I can give some more tips

Hello again , I need your tips now , I am struggling while searching in database, please give me some advice, thank you.