PERF: value_counts_float64 #10821
State: closed

Adresses #10821 - I get a doubling of performance for `value_counts` for a `Series` with a float dtype.  Couldn't think of any new tests needed not covered by existing [here](https://github.com/pydata/pandas/blob/master/pandas/tests/test_algos.py#L416)

```
In [1]: f = np.hstack([np.hstack(np.linspace(0,1,1000)  for _ in range(1000)), np.array([np.nan] * 1000)])
   ...: i = range(1000) * 1001
   ...: df = pd.DataFrame({'f':f, 'i':i})
```
### master

```
In [2]: %timeit df['i'].value_counts()
10 loops, best of 3: 21.1 ms per loop

In [3]: %timeit df['f'].value_counts()
10 loops, best of 3: 114 ms per loop
```
### pr

```
In [3]: %timeit df['i'].value_counts()
10 loops, best of 3: 21 ms per loop

In [2]: %timeit df['f'].value_counts()
10 loops, best of 3: 56 ms per loop
```


Labels:
name: Performance
description: Memory or execution speed performance
name: Dtype Conversions
description: Unexpected or buggy dtype conversions

Comments:
looks pretty good to me...

@chris-b1 can u use fused types (with the int64) one to avoid duplicating code as much as possible
(the types are already defined near the top of the file)

@jreback I'm stuck on how to dispatch to the right `khash` implementation.  Starting out as below, I'm not seeing an obvious way to branch and handle both the `int64` and `float64` case?  Maybe I'm missing something.  Thanks.

```
cpdef value_counts_numeric(sixty_four_bit_scalar[:] values):
    ....
    if sixty_four_bit_scale is float64_t:
        table = ??
```

@chris-b1 yes that is right. see the `append_data` function. This is an odd looking cython syntax for fused type specialization, but apparetnly is a compile type thing. see docs [here](http://docs.cython.org/src/userguide/fusedtypes.html#type-checking-specializations)

@jreback  Sorry, my question wasn't clear - I (somewhat) see how the fused types work, but I'm specifically stuck on accessing the right `khash` functions given a fused type.  Below are things I tried that don't work:

No `cdef` for `table` - cython thinks it's a python object

```
cpdef value_counts_numeric(sixty_four_bit_scalar[:] values):
    ....
    if sixty_four_bit_scalar is float64_t:
        table = kh_init_float64()
```

Conditional `cdef`, which aren't valid.

```
cpdef value_counts_numeric(sixty_four_bit_scalar[:] values):
    ....
    if sixty_four_bit_scalar is float64_t:
        cdef table *kh_float64
        table = kh_init_float64()
```

Fused khash type - invalid to use within a `cdef`

```
ctypedef fused kh_numeric:
    kh_float64_t
    kh_int64_t

cpdef value_counts_numeric(sixty_four_bit_scalar[:] values):
    cdef table * kh_numeric
    if sixty_four_bit_scalar is float64_t:
        table = kh_init_float64()
```

```
ctypedef fused kh_numeric:
    kh_float64_t
    kh_int64_t

cpdef value_counts_numeric(sixty_four_bit_scalar[:] values):
    cdef table * kh_numeric
    if sixty_four_bit_scale is float64_t:
        table = kh_init_float64()
```

doesn't this work?

Doesn't seem to.  Cython actually crashes so the message isn't super helpful (see below), but I figured it was invalid?

```
Error compiling Cython file:
------------------------------------------------------------
...
cpdef value_counts_numeric(sixty_four_bit_scalar[:] values, bint dropna = 0):
    cdef:
        Py_ssize_t i
        sixty_four_bit_scalar[:] result_keys
        int64_t[:] result_counts
        kh_numeric *table
    ^
------------------------------------------------------------

pandas\hashtable.pyx:909:8: Compiler crash in AnalyseDeclarationsTransform

ModuleNode.body = StatListNode(hashtable.pyx:3:0)
StatListNode.stats[38] = StatListNode(hashtable.pyx:904:6)
StatListNode.stats[0] = CompilerDirectivesNode(hashtable.pyx:904:6)
CompilerDirectivesNode.body = StatListNode(hashtable.pyx:904:6)
StatListNode.stats[0] = CFuncDefNode(hashtable.pyx:904:6,
    args = [...]/2,
    decorators = [...]/0,
    has_fused_arguments = True,
    modifiers = [...]/0,
    overridable = 1,
    visibility = u'private')
FusedCFuncDefNode.stats[0] = CFuncDefNode(hashtable.pyx:904:6,
    args = [...]/2,
    decorators = [...]/0,
    modifiers = [...]/0,
    overridable = 1,
    visibility = u'private')
File 'Nodes.py', line 416, in analyse_declarations: StatListNode(hashtable.pyx:905:4,
    is_terminator = True)
File 'Nodes.py', line 416, in analyse_declarations: StatListNode(hashtable.pyx:906:8)
File 'Nodes.py', line 1282, in analyse_declarations: CVarDefNode(hashtable.pyx:909:8,
    modifiers = [...]/0,
    visibility = u'private')
File 'Nodes.py', line 990, in analyse: CSimpleBaseTypeNode(hashtable.pyx:909:8,
    module_path = [...]/0,
    name = u'kh_numeric',
    signed = 1)

Compiler crash traceback from this point on:
File "C:\Users\Chris\Anaconda\envs\pandas-dev\lib\site-packages\Cython\Compiler\Nodes.py", line 990, in analyse
    type = scope.lookup_type(self.name)
File "C:\Users\Chris\Anaconda\envs\pandas-dev\lib\site-packages\Cython\Compiler\Symtab.py", line 810, in lookup_type
    return entry.type.specialize(self.fused_to_specific)
File "C:\Users\Chris\Anaconda\envs\pandas-dev\lib\site-packages\Cython\Compiler\PyrexTypes.py", line 1357, in specialize
    return values[self]
KeyError: FusedType(name=u'kh_numeric')
```

@chris-b1 hmm, not real familiar why you can't do this. Let me have a couple of people look at it. If you make progress, lmk.

cc @insertinterestingnamehere any idea how to specify fused types?

```
cdef:
    kh_int64_t * table_int
    kh_float64_t * table_float
```

`cdef` both, then use the appropriate one.  If you don't want to `cdef` both, then include `kh_numeric` in the signature as a dummy arg and use indexing to dispatch from the one argument version.

@jreback I just tried doing this myself and see the same error. The syntax @chris-b1 used is correct, but Cython isn't handling it correctly. I'm looking for a workaround now.

Okay, on second thought, the problem is that Cython can't determine which version of the fused khash type to use when the pointer is declared. The approach suggested by @kawochen is probably the simplest. I'll see if there's a nice way to tie it all together.

Yes. You could make it visible in the signature and then dispatch to the right version, but I don't know if saving that one pointer is worth going through the hoops.  

yeh, so if this turns out to be more hoops than worth it....then can just revert. 

@jreback  I was just comparing the two approaches I suggested.  The first one seems effective enough -- just one extra pointer. 

Okay, fused types aren't terribly effective when there are so many type-specific function calls in the core part of each function, but I was able to simplify things a little. I'm chasing down some test failures now, but you can get the main idea of what this would look like from what I have thus far. https://github.com/insertinterestingnamehere/pandas/commit/009f4df01cadc32fe7a6b3809174aa81735b7f05 shows how to combine the `value_count` routines, and https://github.com/insertinterestingnamehere/pandas/commit/f28a443f7ead3cfd08ca857294fe289cf17f1c4a shows how to do that for the `build_count_table` routines. To get the latter building properly, a bunch of casts to and from void pointers were necessary since there isn't currently a good way to make fused types depend on one another. I'd recommend only using fused types for the `val_count` functions since it makes the code more concise without complicating things too much.

Alright, https://github.com/insertinterestingnamehere/pandas/commit/8ae9b9af259e3b1f6ab1f56b3d43abc04535fe33 and https://github.com/insertinterestingnamehere/pandas/commit/b9b54ae00eaa4278e0949f4df7da7cbf4aaedd34 should do nicely. Feel free to cherry pick the first or both of them as needed.

Another idea just occurred to me. The type casts can be avoided by allowing the distinct fused types to expand fully and then throwing an error if the wrong combination is used. https://github.com/insertinterestingnamehere/pandas/commit/ba85304acff1f3096056e64e819be3ef3c4483cf does that. That makes it all a lot cleaner. Would you like me to make a PR against the branch used here?

Sounds good to me, or I can pull it in this evening if you don't get a
chance. Thanks for helping with this!
On Aug 18, 2015 3:13 PM, "Ian Henriksen" notifications@github.com wrote:

> Another idea just occurred to me. The type casts can be avoided by
> allowing the distinct fused types to expand fully and then throwing an
> error if the wrong combination is used. insertinterestingnamehere@ba85304
> https://github.com/insertinterestingnamehere/pandas/commit/ba85304acff1f3096056e64e819be3ef3c4483cf
> does that. That makes it all a lot cleaner. Would you like me to make a PR
> against the branch used here?
> 
> —
> Reply to this email directly or view it on GitHub
> https://github.com/pydata/pandas/pull/10840#issuecomment-132336277.

No problem. Here it is: https://github.com/chris-b1/pandas/pull/1. I squashed the `build_count_table` edits into a single commit there as well.

thanks @chris-b1 @insertinterestingnamehere @kawochen 

ping when green.

@jreback Alright. It's finished. Thanks!

thank you all!