{"metadata":{"kernelspec":{"language":"python","display_name":"Python 3","name":"python3"},"language_info":{"pygments_lexer":"ipython3","nbconvert_exporter":"python","version":"3.6.4","file_extension":".py","codemirror_mode":{"name":"ipython","version":3},"name":"python","mimetype":"text/x-python"}},"nbformat_minor":4,"nbformat":4,"cells":[{"cell_type":"markdown","source":"I have been working on performance for some cosine similarity implementations and I want to share results.\n \nI will use as a benchmark a 10_000 x 2_048 float32 matrix for index embedding and a 2_000 x 2_048 float32 matrix for query embedding.\n\nThe result will be a matrix 2_000 x 10_000 which will contain in row *i* and column *j* the cosine similarity of *i*-query for *j*  -index.\n\nQuery and index embeddings are true global features extracted through DELG and cached on disk.\n\nData can't fit all in memory.\n\nI will try 3 implementations:  \n\n* Cosine Similarity with Scipy (Sequential)\n* Cosine Similarity with Scipy (Batch on CPU)\n* Cosine Similarity with TensorFlow (Batch on GPU)\n\nLet's go ! ","metadata":{"papermill":{"duration":0.00587,"end_time":"2020-09-07T15:53:39.012571","exception":false,"start_time":"2020-09-07T15:53:39.006701","status":"completed"},"tags":[]}},{"cell_type":"code","source":"import numpy as np \nimport joblib","metadata":{"_cell_guid":"b1076dfc-b9ad-4769-8c92-a6c4dae69d19","_uuid":"8f2839f25d086af736a60e9eeb907d3b93b6e0e5","execution":{"iopub.execute_input":"2020-09-07T15:53:39.025898Z","iopub.status.busy":"2020-09-07T15:53:39.02513Z","iopub.status.idle":"2020-09-07T15:53:39.121037Z","shell.execute_reply":"2020-09-07T15:53:39.120432Z"},"papermill":{"duration":0.104121,"end_time":"2020-09-07T15:53:39.121151","exception":false,"start_time":"2020-09-07T15:53:39.01703","status":"completed"},"tags":[],"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"def batch_generator (embeddings, batch_size=1000):\n    start = 0\n    stop = 0\n    while stop < embeddings.shape[0] :\n        stop = stop + batch_size\n        yield embeddings[start:stop]\n        start = stop\n        \n        \ntrain_embeddings = joblib.load(\"../input/glr2020-data-for-cosine-similarity/train_embeddings.joblib\")\ntest_embeddings = joblib.load(\"../input/glr2020-data-for-cosine-similarity/test_embeddings.joblib\")\n\nprint(f'train_embeddings:{train_embeddings.shape}, test_embeddings:{test_embeddings.shape}')\n","metadata":{"_cell_guid":"79c7e3d0-c299-4dcb-8224-4455121ee9b0","_uuid":"d629ff2d2480ee46fbb7e2d37f6b5fab8052498a","execution":{"iopub.execute_input":"2020-09-07T15:53:39.13669Z","iopub.status.busy":"2020-09-07T15:53:39.136044Z","iopub.status.idle":"2020-09-07T15:53:39.405161Z","shell.execute_reply":"2020-09-07T15:53:39.40594Z"},"papermill":{"duration":0.280414,"end_time":"2020-09-07T15:53:39.406121","exception":false,"start_time":"2020-09-07T15:53:39.125707","status":"completed"},"tags":[],"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"## Scipy (Sequential CPU)","metadata":{"papermill":{"duration":0.004898,"end_time":"2020-09-07T15:53:39.416592","exception":false,"start_time":"2020-09-07T15:53:39.411694","status":"completed"},"tags":[]}},{"cell_type":"markdown","source":"This is the slow \"for loop\" way. For each test query we calculate the cosine similarity for all the elements of the index - with a for loop - using the scipy function `spatial.distance.cdist` which calculates the cosine distance between vectors.\n\nThe advantage of this methow is the low footprint memory usage: it uses 2048 * (1 + len (train_embeddings)) *  float32 of memory for each cycle.","metadata":{"papermill":{"duration":0.004732,"end_time":"2020-09-07T15:53:39.428065","exception":false,"start_time":"2020-09-07T15:53:39.423333","status":"completed"},"tags":[]}},{"cell_type":"code","source":"%%time\nfrom scipy import spatial\n\nscipy_similarity = np.zeros ((test_embeddings.shape[0], train_embeddings.shape[0]))\n\nfor test_index in range(test_embeddings.shape[0]):\n    scipy_similarity[test_index] = 1 - spatial.distance.cdist(\n        test_embeddings[np.newaxis, test_index, :], train_embeddings,\n        'cosine')[0]\n    \n","metadata":{"execution":{"iopub.execute_input":"2020-09-07T15:53:39.443363Z","iopub.status.busy":"2020-09-07T15:53:39.442598Z","iopub.status.idle":"2020-09-07T15:54:55.355421Z","shell.execute_reply":"2020-09-07T15:54:55.35629Z"},"papermill":{"duration":75.923672,"end_time":"2020-09-07T15:54:55.356519","exception":false,"start_time":"2020-09-07T15:53:39.432847","status":"completed"},"tags":[],"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"## Scipy (Batch CPU)","metadata":{"papermill":{"duration":0.006623,"end_time":"2020-09-07T15:54:55.370702","exception":false,"start_time":"2020-09-07T15:54:55.364079","status":"completed"},"tags":[]}},{"cell_type":"markdown","source":"In this case we use scipy's numpy vectorization of `spatial.distance.cdist`.\n\nWe are forced to perform the calculation in several batches, because all data don't fit in memory.","metadata":{"papermill":{"duration":0.006068,"end_time":"2020-09-07T15:54:55.383202","exception":false,"start_time":"2020-09-07T15:54:55.377134","status":"completed"},"tags":[]}},{"cell_type":"code","source":"%%time\n\nfrom scipy import spatial\n\n\nbatch_scipy_similarity = np.zeros ((test_embeddings.shape[0], train_embeddings.shape[0]))\n\n\ntest_batch_size=500\ntrain_batch_size=1000\nfor i, test_emb in enumerate(batch_generator (test_embeddings, batch_size=test_batch_size)):\n    for j, train_emb in enumerate(batch_generator (train_embeddings, batch_size=train_batch_size)):\n        batch_scipy_similarity[i*test_batch_size:(i+1)*min(test_batch_size,test_emb.shape[0]),\n                      j*train_batch_size:(j+1)*min(train_batch_size,train_emb.shape[0])] =  1 - spatial.distance.cdist(\n                                        test_emb, train_emb,\n                                        'cosine')\n","metadata":{"execution":{"iopub.execute_input":"2020-09-07T15:54:55.405672Z","iopub.status.busy":"2020-09-07T15:54:55.404825Z","iopub.status.idle":"2020-09-07T15:55:23.80321Z","shell.execute_reply":"2020-09-07T15:55:23.804264Z"},"papermill":{"duration":28.414763,"end_time":"2020-09-07T15:55:23.804449","exception":false,"start_time":"2020-09-07T15:54:55.389686","status":"completed"},"tags":[],"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"## check difference \nnp.sum( np.abs (scipy_similarity) - np.abs(batch_scipy_similarity))","metadata":{"execution":{"iopub.execute_input":"2020-09-07T15:55:23.830808Z","iopub.status.busy":"2020-09-07T15:55:23.829946Z","iopub.status.idle":"2020-09-07T15:55:24.00894Z","shell.execute_reply":"2020-09-07T15:55:24.008416Z"},"papermill":{"duration":0.197867,"end_time":"2020-09-07T15:55:24.009052","exception":false,"start_time":"2020-09-07T15:55:23.811185","status":"completed"},"tags":[],"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"## TensorFlow (Batch GPU)","metadata":{"papermill":{"duration":0.004826,"end_time":"2020-09-07T15:55:24.018954","exception":false,"start_time":"2020-09-07T15:55:24.014128","status":"completed"},"tags":[]}},{"cell_type":"markdown","source":"Cosine similarity is the cosine of the angle between two vectors, which is also the same as the inner product of the same vectors normalized to both have length 1: we can compute it with TensorFlow using `tf.reduce_sum` and `tf.norm`.\n\nIn this way we use the GPU managed by TensorFlow instead of CPU.","metadata":{"papermill":{"duration":0.004583,"end_time":"2020-09-07T15:55:24.028238","exception":false,"start_time":"2020-09-07T15:55:24.023655","status":"completed"},"tags":[]}},{"cell_type":"code","source":"%%time\n\nimport tensorflow as tf\nimport numpy as np\n\n\ntf_similarity = np.zeros ((test_embeddings.shape[0], train_embeddings.shape[0]))\n\n\ntest_batch_size=500\ntrain_batch_size=1000\nfor i, test_emb in enumerate(batch_generator (test_embeddings, batch_size=test_batch_size)):\n    for j, train_emb in enumerate(batch_generator (train_embeddings, batch_size=train_batch_size)):\n        \n\n        b = tf.constant (train_emb)\n        a = tf.constant (test_emb)\n\n        similarity = tf.reduce_sum(a[:, tf.newaxis] * b, axis=-1)\n        similarity /= tf.norm(a[:, tf.newaxis], axis=-1) * tf.norm(b, axis=-1)\n        \n        tf_similarity[i*test_batch_size:(i+1)*min(test_batch_size,test_emb.shape[0]),\n                      j*train_batch_size:(j+1)*min(train_batch_size,train_emb.shape[0])] = similarity.numpy()\n\n\n","metadata":{"execution":{"iopub.execute_input":"2020-09-07T15:55:24.045305Z","iopub.status.busy":"2020-09-07T15:55:24.04467Z","iopub.status.idle":"2020-09-07T15:55:35.162485Z","shell.execute_reply":"2020-09-07T15:55:35.163136Z"},"papermill":{"duration":11.130143,"end_time":"2020-09-07T15:55:35.163282","exception":false,"start_time":"2020-09-07T15:55:24.033139","status":"completed"},"tags":[],"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"## check difference \nnp.sum(np.abs(scipy_similarity) - np.abs(tf_similarity))","metadata":{"execution":{"iopub.execute_input":"2020-09-07T15:55:35.180377Z","iopub.status.busy":"2020-09-07T15:55:35.178802Z","iopub.status.idle":"2020-09-07T15:55:35.323963Z","shell.execute_reply":"2020-09-07T15:55:35.324446Z"},"papermill":{"duration":0.155992,"end_time":"2020-09-07T15:55:35.324607","exception":false,"start_time":"2020-09-07T15:55:35.168615","status":"completed"},"tags":[],"trusted":true},"execution_count":null,"outputs":[]}]}