If the C version is to remain in Python3.5, please make sure it provides all of the carefully designed features of the pure python version:

   * The hash function is called no more than once per element
   * The key is constructed to be flat as possible
   * Thread-safe where needed:
     - make_key called outside locks 
     - within a reentrant lock (either a real lock or the GIL),
       check to see if the key is in the cache and if so, 
       update the stats and return the value
     + outside of locks, call the user function
       (allowing for recursive functions)
     + within a reentrant lock (either a real lock or the GIL)
       handle cache misses by 1) verifying there was not an
       intervening cache update by the user function, 2)
       updating links, 3) updating stats.  During the updates,
       make only one potentially reentrant cache[key]
       assignment after all invariants have been restored.
       Save all decrefs until all other state updates
       have been completed.

A number of features of the lru_cache were designed for space savings over speed (lru is all about eviction to make space for a new entry), for thread safety and to not fall apart during reentrancy. It also provides a guarantee that the hash function is not called more than once per element and is called *before* any of the lru structure updates or lookups (this makes reasoning about correctness *much* easier).

In these capabilities can't be reliably reproduced for 3.5, I think the whole thing should be reverted and deferred to 3.6.