CLN: revisit & simplify Block/BlockManager, remove axes
State: closed

This is a WIP request for Stage 1 deliverable of #6744.

Roadmap:
- [x] make ref_locs primary source of information (leaving items/ref_items in place to back it up and avoid breakage)
- [x] port groupby  to loc-based implementation (there's quite a number of hacks a.t.m. that make this non-trivial)
- [x] ditto for merge/join/concat
- [x] ditto for io code
- [x] ditto for reshape
- [x] clean up Block `items`
- [x] clean up Block `ref_items`
- [x] fix performance issues & integrate with mainline


Labels:
name: Refactor
description: Internal refactoring of code
name: Indexing
description: Related to indexing on series/frames, not to indexes themselves
name: Internals
description: Related to non-user accessible pandas implementation

Comments:
whoosh! cleans up a lots of code
how's perf?
some of the slots in BlockManager eg ndim/shape were to fix perf FYI 
(I think u r caching thrn now so maybe ok)

Thanks for the info, I'm pretty sure it's a lot slower right now, but I'm going to address performance when the situation stabilizes.  As of now, it's breakage everywhere.

ok np

but the general concept seems like a nice idea

does make it a lot simpler so big +1 in that

perf will come

iirc their is an OrdersDict somewhere in compat (so that fixes the. 2.6 errors)

@jreback, one of timeseries-related slow tests fails under weird circumstances on py2.6, any idea on why that may happen? I tried to troubleshoot that but to no avail.

that uses numpy 1.6.1, maybe set up a virtual env to debug. 

Their is some coercion in make_block to make sure that a datetime-like is actually coerced to the DatetimeBlock (normally this coercion happens upon in _sanitize_array), but their are cases like this (e.g. insertion to a DataFrame), when that is not called (and the coercion happens in make_block). I on't recall the exact reason that _sanitize_array is NOT used. It might be that is the best soln and eliminate the coercion in make_block.

> that uses numpy 1.6.1, maybe set up a virtual env to debug. 

Yeah, I figured that out from logs, although I did install some dependencies by hand...

So, the branch has been green for quite a while, there's still some cleanup potential, but in terms of functionality it's complete.  Several issues still exist though:
- I sorely miss RangeIndex class since using it as mgr-locs (block-side part of "flexible axis" structure) would allow a lot of optimization without altering any code. I'm hacking the most urgent bits of it in BlockPlacement class, but I'm not proud of how it looks.
- There are some corner cases with inherently dreadful performance, e.g. inserting 500 columns at the end of a dataframe, which has slowed due to 500 updates of ref-loc array. This particular case is worked around easily by postponing ref-loc finalization, but the effort to keep the proper structure "in air" increases dramatically if operations stack. Naturally, I'd use some rope-like data structure, but I'm reluctant to re-implement it from scratch myself, but OTOH I assume the idea to add 3rdparty dependencies must gain traction before being approved.

any perf issues?

if u find a 3rd party library that has a compatible license (bsd) and it can be fully incorporated then it's ok to include

it would be shipped inline with pandas (kind of like ujson / msgpack / khash stuff)

if u have something in mind put up a link and I'll take a look

I don't think the mode should be changed on the computation/tests/test_eval.py

I turn off all mode changing to the repor FYI
;of course to fix you have to change it and push then re disable)

@immerr - okay I got part way through adding a range index. I'll see if I can dust it off soon. Not sure if you want to wait though.

@jtratner that's awesome, I'm fine with using BlockPlacement for now but I look forward to dropping that kludge in favour of what you're going to implement.

@jreback, I don't see any computation/tests directory there... where should I look?

it's the first file in the changes list (it's the mode that is changed)

Ahh, will fix, thanks

ping when you want me to look again

and squash as appropraite

There's something weird with how sparse blocks handle reindexing:

``` python

In [1]: pd.__version__
Out[1]: '0.13.1'

In [2]: pd.DataFrame({'a': pd.SparseArray([1,2,3, np.nan, np.nan]), 'b': [1,2,3,np.nan,np.nan]})
Out[2]: 
    a   b
0   1   1
1   2   2
2   3   3
3 NaN NaN
4 NaN NaN

[5 rows x 2 columns]

In [3]: _2.reindex(_2.index[1:], fill_value=10.)
Out[3]: 
    a   b
1   2   2
2   3   3
3  10 NaN
4  10 NaN

[4 rows x 2 columns]

```

I thought this was a result of my intervention, but this occurs in upstream, too. @jreback, is this expected?

Ok, this has to be a bug...

``` python
In [4]: _2.reindex(_2.index[1:], fill_value='foo')
---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
<ipython-input-3-a9f0316534b7> in <module>()
----> 1 _2.reindex(_2.index[1:], fill_value='foo')

/home/immerrr/.conda/envs/py33/lib/python3.3/site-packages/pandas/core/frame.py in reindex(self, index, columns, **kwargs)
   2160     def reindex(self, index=None, columns=None, **kwargs):
   2161         return super(DataFrame, self).reindex(index=index, columns=columns,
-> 2162                                               **kwargs)
   2163 
   2164     @Appender(_shared_docs['reindex_axis'] % _shared_doc_kwargs)

/home/immerrr/.conda/envs/py33/lib/python3.3/site-packages/pandas/core/generic.py in reindex(self, *args, **kwargs)
   1563         return self._reindex_axes(axes, level, limit,
   1564                                   method, fill_value, copy,
-> 1565                                   takeable=takeable).__finalize__(self)
   1566 
   1567     def _reindex_axes(self, axes, level, limit, method, fill_value, copy,

/home/immerrr/.conda/envs/py33/lib/python3.3/site-packages/pandas/core/frame.py in _reindex_axes(self, axes, level, limit, method, fill_value, copy, takeable)
   2115         if index is not None:
   2116             frame = frame._reindex_index(index, method, copy, level,
-> 2117                                          fill_value, limit, takeable=takeable)
   2118 
   2119         return frame

/home/immerrr/.conda/envs/py33/lib/python3.3/site-packages/pandas/core/frame.py in _reindex_index(self, new_index, method, copy, level, fill_value, limit, takeable)
   2127         return self._reindex_with_indexers({0: [new_index, indexer]},
   2128                                            copy=copy, fill_value=fill_value,
-> 2129                                            allow_dups=takeable)
   2130 
   2131     def _reindex_columns(self, new_columns, copy, level, fill_value=NA,

/home/immerrr/.conda/envs/py33/lib/python3.3/site-packages/pandas/core/generic.py in _reindex_with_indexers(self, reindexers, method, fill_value, limit, copy, allow_dups)
   1689                 new_data = new_data.reindex_indexer(index, indexer, axis=baxis,
   1690                                                     fill_value=fill_value,
-> 1691                                                     allow_dups=allow_dups)
   1692 
   1693             elif (baxis == 0 and index is not None and

/home/immerrr/.conda/envs/py33/lib/python3.3/site-packages/pandas/core/internals.py in reindex_indexer(self, new_axis, indexer, axis, fill_value, allow_dups)
   3249         for block in self.blocks:
   3250             newb = block.reindex_axis(
-> 3251                 indexer, axis=axis, fill_value=fill_value)
   3252             new_blocks.append(newb)
   3253 

/home/immerrr/.conda/envs/py33/lib/python3.3/site-packages/pandas/core/internals.py in reindex_axis(self, indexer, method, axis, fill_value, limit, mask_info)
   1878             fill_value = self.fill_value
   1879         return self.make_block(self.values.take(indexer), items=self.items,
-> 1880                                fill_value=fill_value)
   1881 
   1882     def reindex_items_from(self, new_ref_items, indexer=None, method=None,

/home/immerrr/.conda/envs/py33/lib/python3.3/site-packages/pandas/core/internals.py in make_block(self, values, items, ref_items, sparse_index, kind, dtype, fill_value, copy, fastpath)
   1827         new_values = SparseArray(values, sparse_index=sparse_index,
   1828                                  kind=kind or self.kind, dtype=dtype,
-> 1829                                  fill_value=fill_value, copy=copy)
   1830         return make_block(new_values, items, ref_items, ndim=self.ndim,
   1831                           fastpath=fastpath)

/home/immerrr/.conda/envs/py33/lib/python3.3/site-packages/pandas/sparse/array.py in __new__(cls, data, sparse_index, index, kind, fill_value, dtype, copy)
    150             if sparse_index is None:
    151                 values, sparse_index = make_sparse(data, kind=kind,
--> 152                                                    fill_value=fill_value)
    153             else:
    154                 values = data

/home/immerrr/.conda/envs/py33/lib/python3.3/site-packages/pandas/sparse/array.py in make_sparse(arr, kind, fill_value)
    509     length = len(arr)
    510 
--> 511     if np.isnan(fill_value):
    512         mask = -np.isnan(arr)
    513     else:

TypeError: Not implemented for this type

```

the reindex looks like a bug
but your last example is not
you can't fill with a string as it's not supported ATM
only floats are well tested
in theory this should work but would need a fair amount of effort

> the reindex looks like a bug

reported it as #6949, do you want me to fix this upstream before fixing in this branch?

sure
anything u can fix in separate issues do so 

@immerrr did you have any perf issues remaining? this needs to be merged asap...so we have a little time in master before rc....or could push to 0.14.1 (prob 1 month after release)

There still are some corner cases, https://gist.github.com/immerrr/11253953. On the bright side, it's quite a bit faster on duplicate indices:

``` python
In [9]: df = pd.DataFrame(np.random.randn(1000, 1000), columns=np.ones(1000), index=np.zeros(1000))

In [10]: timeit df.iloc[:, :500]
10000 loops, best of 3: 109 µs per loop

In [11]: timeit df.iloc[:500, :]
10000 loops, best of 3: 106 µs per loop
```

VS 

``` python

In [1]: df = pd.DataFrame(np.random.randn(1000, 1000), columns=np.ones(1000), index=np.zeros(1000))

In [2]: timeit df.iloc[:, :500]
1000 loops, best of 3: 355 µs per loop

In [3]: timeit df.iloc[:500, :]
1000 loops, best of 3: 536 µs per loop

```

@jreback, I think I have addressed most (all?) of 2x slowdowns and now maximum performance impact is about 20-30%.

Did break some tests on the way, will see to them and rebase tonight.

ok ping when ready and squash somewhat 

@jreback, rebased and green

ok...bombs away

and joy you get to support this going forward :)