{"action":"created","issue":{"url":"https://api.github.com/repos/Blosc/bcolz/issues/176","labels_url":"https://api.github.com/repos/Blosc/bcolz/issues/176/labels{/name}","comments_url":"https://api.github.com/repos/Blosc/bcolz/issues/176/comments","events_url":"https://api.github.com/repos/Blosc/bcolz/issues/176/events","html_url":"https://github.com/Blosc/bcolz/issues/176","id":69446509,"number":176,"title":"Pandas out_flavor for better ctable performance","user":{"login":"ARF1","id":5834577,"avatar_url":"https://avatars.githubusercontent.com/u/5834577?v=3","gravatar_id":"","url":"https://api.github.com/users/ARF1","html_url":"https://github.com/ARF1","followers_url":"https://api.github.com/users/ARF1/followers","following_url":"https://api.github.com/users/ARF1/following{/other_user}","gists_url":"https://api.github.com/users/ARF1/gists{/gist_id}","starred_url":"https://api.github.com/users/ARF1/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/ARF1/subscriptions","organizations_url":"https://api.github.com/users/ARF1/orgs","repos_url":"https://api.github.com/users/ARF1/repos","events_url":"https://api.github.com/users/ARF1/events{/privacy}","received_events_url":"https://api.github.com/users/ARF1/received_events","type":"User","site_admin":false},"labels":[],"state":"open","locked":false,"assignee":null,"milestone":null,"comments":1,"created_at":"2015-04-19T17:26:54Z","updated_at":"2015-04-19T20:28:44Z","closed_at":null,"body":"In this issue I want to make the case for the extension of the effect of `out_flavor` to `__getitem__()` (and related functions) and the introduction of a `pandas` outflavor. While I appreciate the rationale for limiting bcolz to the numpy data model I believe the possible performance improvements with pandas merit consideration.\r\n\r\nI would be very interested to know if this has any chance for inclusion in bcolz, since the effort would be non-trivial for a clean implementation.\r\n\r\n### Executive Summary ###\r\n - bcolz is a columnar (albeit chunked) data container\r\n - thus after decompression of each chunk, the data for each column is (chunk-)contiguous\r\n - currently however, this column-contiguous data is forced into a row-major memory structure (numpy structured array)\r\n - this has two consequences:\r\n   1. the contiguous column-data has to be copied in row-sized chunks which is much slower than en-bloc copying of contiguous data,\r\n   2. the data has to be copied (rather than being decompressed directly into the \"proper\" place)\r\n - Moving to a column-major memory layout (e.g. pandas DataFrame) would provide:\r\n   1. much faster assignment of data to colums (which is a very common operation with `ctable`)\r\n   2. opens the possibility for avoiding repeated copy operations in the first place\r\n   3. ctable would be able to really leverage multi-core machines. Currently the numpy structured array is a bottleneck for `__getitem__()` and the like: #174\r\n   4.  improve down-stream performance of data analysis as much data analysis is carried out along column rather than along rows\r\n -  due to the similar data access model of numpy structured arrays and pandas dataframes most code could probably remain unchanged after the output data object is initialised either as `numpy` or `pandas`\r\n \r\n### Evidence of column assignment bottleneck ###\r\nNote: for the sake of simplicity, when I use the term \"column\" in relation to numpy structured arrays, I refer to the fields of the (single column) structured array that bcolz uses to store its output column.\r\n\r\nNumpy structured arrays (as used by bcolz) are inherently row-major. It is impossible to change this as far as I can see. This means that column assignment is fairly slow:\r\n```\r\nIn [1]: import numpy as np\r\n\r\nIn [2]: M,N=int(1e7),10\r\n\r\n# make a row-major numpy array\r\n\r\nIn [4]: A1=np.zeros((M,N),'f')\r\n\r\nIn [9]: dt=np.dtype(','.join(['f' for _ in range(N)]))\r\n\r\n# make a structured numpy array\r\n\r\nIn [10]: A2=np.zeros((M,),dtype=dt)\r\n\r\nIn [11]: X=np.arange(M+0.0)\r\n\r\n### simulate ctable __getitem()__ operation:\r\n# assignment to a row-major numpy array column for column\r\n\r\nIn [13]: %timeit for n in range(N):A1[:,n]=X\r\n1 loops, best of 3: 2.36 s per loop\r\n\r\n# assignment of structured array field for field\r\n\r\nIn [15]: %timeit for n in dt.names: A2[n]=X\r\n1 loops, best of 3: 2.36 s per loop\r\n```\r\n\r\nSignificant speedup (factor 6.5!) can be achieved by moving to a column-major memory layout for the numpy array:\r\n```\r\nIn [1]: import numpy as np\r\n\r\nIn [2]: M,N=int(1e7),10\r\n\r\n# make a colum-major numpy array\r\nIn [3]: A1=np.zeros((M,N),'f', 'F')\r\n\r\nIn [4]: dt=np.dtype(','.join(['f' for _ in range(N)]))\r\n\r\n# make a structured numpy array\r\n\r\nIn [5]: A2=np.zeros((M,),dtype=dt)\r\n\r\nIn [6]: X=np.arange(M+0.0)\r\n\r\n### simulate ctable __getitem()__ operation:\r\n# assignment to a column-major numpy array column for column\r\n\r\nIn [8]: %timeit for n in range(N):A1[:,n]=X\r\n1 loops, best of 3: 374 ms per loop\r\n\r\n# assignment of structured array field for field\r\n\r\nIn [9]: %timeit for n in dt.names: A2[n]=X\r\n1 loops, best of 3: 2.43 s per loop\r\n```\r\n\r\n### Why Pandas DataFrames would help ###\r\nWhile moving to column-major numpy arrays would be the ideal solution, this is obviously not an option: they require the entire array to have a homogeneous dtype.\r\n\r\nPandas DataFrame however supports columns of different dtypes and by design stores data in column-major order. (As I remember because Wes McKinney said that most of his data analysis happened along columns, though I cannot find the reference. That said I think the following article in which he explains his reasons for not choosing numpy structured arrays is interesting: [Wes McKinney: A Roadmap for Rich Scientific Data Structures in Python](http://wesmckinney.com/blog/a-roadmap-for-rich-scientific-data-structures-in-python/))\r\n\r\nIn addition, the choice of column-major ordering permits size-mutability: columns can be added without copying the data. This fits well with the ctable column-store philosopy. With numpy structured arrays, the entire array has to be copied (almost entry by entry as far as I can see) to add a new column.\r\n\r\nDue to these advantages, column-major ordering is used my many well-known dedicated number crunching environments, among others: Fortran, MATLAB and R\r\n\r\nNote: Making a pandas DataFrame for an already existing numpy structured array returned by ctable is not an option either: again, effectively element by element copying of the data is required.\r\n\r\n### Evidence of performance improvements with Pandas ###\r\n\r\nInstantiation of Pandas DataFrames is admittedly an issue with smaller databases. Leaving this issue aside for the moment, one can see that assignment to an (instantiated DataFrame) is much faster:\r\n\r\n```\r\nIn [1]: import numpy as np\r\n\r\nIn [2]: import pandas as pd\r\n\r\nIn [3]: M,N=int(1e7),10\r\n\r\nIn [4]: A1=np.zeros((M,N),'f', 'F')\r\n\r\nIn [5]: dt=np.dtype(','.join(['f' for _ in range(N)]))\r\n\r\nIn [6]: A2=np.zeros((M,),dtype=dt)\r\n\r\nIn [7]: X=np.arange(M+0.0)\r\n\r\n# make a pandas DataFrame\r\n\r\nIn [8]: df_A1 = pd.DataFrame(index=xrange(M), columns=range(N), dtype='f')\r\n\r\n### simulate ctable __getitem()__ operation:\r\n# assignment to a column-major numpy array column for column\r\n\r\nIn [9]: %timeit for n in range(N): A1[:,n]=X\r\n1 loops, best of 3: 369 ms per loop\r\n\r\n# assignment to a structured numpy array field for field\r\n\r\nIn [10]: %timeit for n in dt.names: A2[n]=X\r\n1 loops, best of 3: 2.36 s per loop\r\n\r\n# (optimized) assignment to a pandas DataFrame column for column\r\n\r\nIn [8]: %timeit for n in range(N): df_A1._data.blocks[0].values[n,:]=X\r\n1 loops, best of 3: 364 ms per loop\r\n```\r\n\r\nInstantiation of the DataFrame will probably be an issue. My gut reaction is that it should be possible to instantiate (and cache) an empty DataFrame with the correct structure and then for each `__getitem__()` call shallow-copy this template and assign new data arrays. This should help with the instantiation overhead, since the column makeup of a ctable instance usually does not change too often during a program.\r\n\r\n### Down the road ###\r\nIn the long run it might be worth getting rid of the memory copies altogether for DataFrame out_flavor and decopressing the chunks directly into the arrays backing the DataFrame. This would likely lead to further performance improvements (though smaller as the remaining memory copies would already be efficient en-bloc copies)."},"comment":{"url":"https://api.github.com/repos/Blosc/bcolz/issues/comments/94310692","html_url":"https://github.com/Blosc/bcolz/issues/176#issuecomment-94310692","issue_url":"https://api.github.com/repos/Blosc/bcolz/issues/176","id":94310692,"user":{"login":"ARF1","id":5834577,"avatar_url":"https://avatars.githubusercontent.com/u/5834577?v=3","gravatar_id":"","url":"https://api.github.com/users/ARF1","html_url":"https://github.com/ARF1","followers_url":"https://api.github.com/users/ARF1/followers","following_url":"https://api.github.com/users/ARF1/following{/other_user}","gists_url":"https://api.github.com/users/ARF1/gists{/gist_id}","starred_url":"https://api.github.com/users/ARF1/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/ARF1/subscriptions","organizations_url":"https://api.github.com/users/ARF1/orgs","repos_url":"https://api.github.com/users/ARF1/repos","events_url":"https://api.github.com/users/ARF1/events{/privacy}","received_events_url":"https://api.github.com/users/ARF1/received_events","type":"User","site_admin":false},"created_at":"2015-04-19T20:28:44Z","updated_at":"2015-04-19T20:28:44Z","body":"See also FrancescAlted's comment on this issue in [#66](http://github.com/Blosc/bcolz/issues/66#issuecomment-94306148)."}}