classification
Title: Add half-float (16-bit) support to struct module
Type: enhancement Stage: patch review
Components: Library (Lib) Versions: Python 3.3
process
Status: open Resolution:
Dependencies: Superseder:
Assigned To: mark.dickinson Nosy List: Eli.Stevens, asvetlov, belopolsky, mark.dickinson, mark.wiebe, paulehoffman, pitrou
Priority: normal Keywords: patch

Created on 2011-04-01 01:00 by Eli.Stevens, last changed 2013-05-06 11:02 by mark.dickinson.

Files
File name Uploaded Description Edit
cpython-struct-float16-v4.patch Eli.Stevens, 2011-04-05 10:10 Unifies implementation for non IEEE platforms, adds docs and tests. review
cpython-struct-float16-v5.patch Eli.Stevens, 2011-04-05 18:08 review
cpython-struct-float16-v6.patch mark.dickinson, 2013-05-06 11:02 review
Messages (32)
msg132722 - (view) Author: Eli Stevens (Eli.Stevens) Date: 2011-04-01 01:00
Numpy 1.6.0 adds support for a half-float (16-bit) data type, but
cannot currently export a buffer interface to the data since neither PEP 3118 nor the struct module (referenced by PEP 3118) support the data type.

I am proposing that the struct module be extended to support half floats, and will be providing a patch that implements that behavior.

The current numpy implementation (1.6.0b1) uses the 'e' character to indicate half floats; I don't have a vested interest in what character is used.  If consensus between CPython and numpy is reached for using a different character, I will update my patches (but I don't plan on participating in the bike shedding prior to that point).

For reference:

python-ideas thread:
http://mail.python.org/pipermail/python-ideas/2011-March/009650.html

numpy-discussion thread:
http://mail.scipy.org/pipermail/numpy-discussion/2011-March/055667.html

cython-user thread (less relevant to this issue specifically):
http://groups.google.com/group/cython-users/browse_thread/thread/6bf811409cdab89e
msg132726 - (view) Author: Eli Stevens (Eli.Stevens) Date: 2011-04-01 01:46
Initial patch; tests pass.  A couple notes:

- I manually excised some commented changes to structmodule.{h,c} from the .patch; once I get a determination on if those files need to be updated or not I will discard the changes or implement what needs to be done there.  Hopefully I didn't damage the patch while editing.

- The code in _PyFloat_Pack2 and _PyFloat_Unpack2 is adapted from the numpy code in https://github.com/numpy/numpy/blob/master/numpy/core/src/npymath/halffloat.c .  This means that it is BSD licensed; I'm presuming that is acceptable for inclusion in CPython.  If not, I'll try a clean-room implementation.
msg132732 - (view) Author: Mark Wiebe (mark.wiebe) Date: 2011-04-01 07:58
Taking a look at the patch, I see you're using the single -> half conversion routine from NumPy. This has the double rounding problem when converting double -> float -> half, so it would be better to use the double -> half routine. I implemented it with 64-bit unsigned ints, so if there are platforms not supporting 64-bit ints, something else such as using the 32-bit routine will have to be done there.
msg132761 - (view) Author: Eli Stevens (Eli.Stevens) Date: 2011-04-01 17:16
I'm thinking of taking the current float implementation and wrapping it with something like:

#if HAS_INT64_TYPE
    // double implementation goes here
#else
    // float implementation here (what's in the current patch)
    ...
#endif

Does this seem like a reasonable approach?

Is there a CPython-canonical way to spell "HAS_INT64_TYPE" and/or find out what type that is on the current platform?
msg132763 - (view) Author: Eli Stevens (Eli.Stevens) Date: 2011-04-01 19:01
I've spelled "HAS_INT64_TYPE" as follows:

+#if SIZEOF_LONG == 8 || SIZEOF_LONG_LONG == 8
+#if SIZEOF_LONG == 8
+    typedef unsigned long npy_uint64;
+#else
+#if SIZEOF_LONG_LONG == 8
+    typedef unsigned long long npy_uint64;
+#endif
+#endif
...

I left the Unpack2 function using floats, since there's no rounding issues there, and it didn't feel like the extra code complexity was justified.  If there's disagreement on that point, I can make a similar change for Unpack2.
msg132764 - (view) Author: Mark Wiebe (mark.wiebe) Date: 2011-04-01 19:13
I think this won't work on Windows since there the 64-bit int is generally __int64.  If you look at the long long and unsigned long long support in _struct.c you can see a better way to do this: "#ifdef HAVE_LONG_LONG" and "unsigned PY_LONG_LONG" for the type.
msg132765 - (view) Author: Eli Stevens (Eli.Stevens) Date: 2011-04-01 19:40
Ahh, yes, much cleaner.  Thank you.  :)  I'll remove the previous version.
msg132942 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2011-04-04 13:35
I've only glanced at the patch, but a couple of things:

(1) It looks as though the patch assumes that a C double is IEEE 754 binary64 format, and that a C float is IEEE 754 binary32 format.  Is that correct?

If so, that's a significant break with tradition:  Python's supposed to be able to work with the native doubles, no matter what their format.  I, for one, wouldn't object if IEEE floating-point were made a requirement for Python >= 3.3, but this change would need to be discussed on the python-dev mailing list.

(2)  The

  typedef PY_LONG_LONG npy_uint64;

looks wrong to me for two reasons:  first, PY_LONG_LONG is a signed type.  Second, while it's guaranteed (by the C standard) that unsigned long long will have width at least 64, it's not guaranteed that it'll be exactly 64.  Does the code depend on this assumption?  Similarly when using unsigned int in the union for the 32-bit code;  here it's not even guaranteed by the standards that unsigned int has width at least 32.

It may be better to use the PY_UINT64_T type and the HAVE_UINT64_T macros, and similarly for the 32-bit types.
msg132961 - (view) Author: Mark Wiebe (mark.wiebe) Date: 2011-04-04 19:12
The patch currently assumes IEEE 754 with byte-order matching the integer type. I see that pyconfig.h defines three possible cases when IEEE 754 doubles are supported, DOUBLE_IS_LITTLE_ENDIAN_IEEE754, DOUBLE_IS_BIG_ENDIAN_IEEE754, and DOUBLE_IS_ARM_MIXED_ENDIAN_IEEE754. The code should have some byte swapping to match it to the integer endianness.

If support for non-IEEE systems is still desired, implementing a conversion using isnan/isinf/frexp/ldexp should be pretty easy, though off hand I can't see an efficient way to extract the significand bits.

Regarding the PY_LONG_LONG, it should have been unsigned PY_LONG_LONG. Using PY_UINT64_T is better, though, since a bigger PY_LONG_LONG would cause trouble in the union.

For the UINT32, maybe just using the double/PY_UINT64_T versions is better, since there is no macro for FLOAT_IS_IEEE754? Falling back to a frexpr implementation if double isn't IEEE or there is no 64-bit integer type may be a reasonable tradeoff to support the few platforms where that's the case, and 2 instead of 3 separate conversion codes is a bit better maintenance-wise.
msg132976 - (view) Author: Eli Stevens (Eli.Stevens) Date: 2011-04-04 21:36
There seems to be some disagreement about the double-rounding issue; Mark Dickinson posted on python-ideas that he doesn't think that there is one.  If possible, I think that removing code paths that aren't needed are generally a good thing, especially if I'm going to have to add support for non-IEEE floats.

I'll start working on the isnan/isinf/frexp/ldexp implementation for the cases where either we don't have a UINT64 type, or doubles aren't IEEE.  Given my current schedule, I don't think that I'll have this done today; hopefully tomorrow morning.  :)
msg132980 - (view) Author: Mark Wiebe (mark.wiebe) Date: 2011-04-04 22:03
There's no disagreement, since they're different cases. Taking an arbitrary double, rounding to float, then rounding to half definitely has double-rounding issues. (And I would recommend constructing an example to add to the test case to make sure you understand what's going on.) Taking two halfs, doing a primitive arithmetic operation on them as floats, then rounding back to half is what Mark was referring to on the list.

In NumPy I also tried to err more towards accuracy and performance than having each intermediate be strictly half. The einsum function retains intermediate values as floats when operating on half, for example, and that's what I recommended in the documentation.

I'd also suggest adding some more to the test suite here to verify that ties are rounding to the nearest even properly. You can see some tests for this here:

https://github.com/numpy/numpy/blob/master/numpy/core/tests/test_half.py#L124
msg133004 - (view) Author: Eli Stevens (Eli.Stevens) Date: 2011-04-05 06:53
I see the distinction about the rounding error now.  Thanks for clarifying; I've added more tests as suggested.

Looking at _struct.c, line 2085:

                    /* Skip float and double, could be
                       "unknown" float format */
                    if (ptr->format == 'd' || ptr->format == 'f')
                        break;
                    ptr->pack = native->pack;
                    ptr->unpack = native->unpack;
                    break;

I'm going to assume that it's okay to allow 'e' to pass through here, since the 'e' type is *always* going to be in IEEE 754 (not "unknown") floating point format, and the handling routines don't rely on the C conversions the way the float/double ones do.  Is that a good assumption to make?

Also, looking at the line in the native_table declaration:

    {'e',       sizeof(short),  SHORT_ALIGN,    nu_halffloat,   np_halffloat},

Does it make sense to have an entry here since there isn't actually a native representation?  ATM it's implemented as just figuring out the platform endianness, and then calling the corresponding lp_/lu_ or bp_/bu_ function.
msg133005 - (view) Author: Eli Stevens (Eli.Stevens) Date: 2011-04-05 07:42
More questions:

The current _PyFloat_Pack4 doesn't round to even:

        fbits = (unsigned int)(f + 0.5); /* Round */

Is the mismatch going to be a problem?  Should I change the _PyFloat_Pack4 implementation while I'm in there?
msg133013 - (view) Author: Eli Stevens (Eli.Stevens) Date: 2011-04-05 10:10
Made the _PyFloat_Pack2 match the algo in _PyFloat_Pack4, and did similar for Unpack.  This should work on platforms that don't have IEEE 754 floats except for situations where an INF or NAN is unpacked (this is the same as the Unpack4 behavior).

This also gets rid of any need for #ifdef'd code (an ad-hoc speed test showed no noticeable difference between the numpy-based version and the CPython-based version of the functions).

I've also added a bit of documentation to this version, as well as more tests.

I haven't changed anything about the native_table entry or Pack4's non-round-to-even behavior.
msg133020 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2011-04-05 11:36
> There's no disagreement, since they're different cases. [...]

What he said.

> Should I change the _PyFloat_Pack4 implementation while I'm in there?

No;  let's keep the patch as simple as possible.  We can open a separate issue for fixing _Pack4 if necessary.  Is the failure to round-to-even only for legacy formats, or is it for IEEE formats as well?  If the former, it's difficult to care much;  if the latter, it should definitely be fixed, but not as part of this issue.

> Made the _PyFloat_Pack2 match the algo in _PyFloat_Pack4, and did
> similar for Unpack.

Thanks;  haven't looked at the new patch yet, but hope to do so in the next few days.
msg133024 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2011-04-05 12:22
> Is the failure to round-to-even only for legacy formats, or is it for
> IEEE formats as well?

Ah;  I see it's just for the non-IEEE formats, so not really an issue.  When the float format is known, the code just depends on a (float) cast doing the right thing, which it generally will.
msg133025 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2011-04-05 12:23
> I'd also suggest adding some more to the test suite here to verify that > ties are rounding to the nearest even properly.

And I second this suggestion.
msg133060 - (view) Author: Eli Stevens (Eli.Stevens) Date: 2011-04-05 18:08
All four changes suggested via review from Mark Dickinson have been made.  One note: the else if (!(e == 0 && f == 0.0)) { change was made; this makes the Pack2 function parallel the Pack4 function slightly less.  I agree that it's cleaner this way, but I've left the original if in as a comment for comparison to Pack4.  I'll remove the comment if it's decided that it's better to be clean than parallel.

The suggested test cases were added in the v4 patch, just in case that wasn't clear.

I'm going to assume that my questions about _struct.c aren't issues unless someone explicitly says they are.

Thanks for all of the review and feedback!  :)
msg133073 - (view) Author: Mark Wiebe (mark.wiebe) Date: 2011-04-05 18:32
Just a few small tweaks.

I think you meant to subtract the second term here:
+    #('>e', b'\x80\x01', -2.0**-25 + 2.0**-35), # Rounds to minimum subnormal

Isn't the "x < 0" part unnecessary? Maybe a comment explaining why the signbit function is used, to preserve -0, would help people who otherwise might think to replace it with "x < 0".
+    if (x < 0 || signbit(x)) {

This is creating a signaling nan. It would be better to create a quiet nan by setting the highest order bit instead of the lowest order bit.
+    else if (isnan(x)) {
+        e = 0x1f;
+        bits = 1;
+    }

Otherwise it looks great to me, good work!
msg133078 - (view) Author: Eli Stevens (Eli.Stevens) Date: 2011-04-05 19:03
Updated patch with changes suggested by Mark Wiebe.  I also removed the commented-out "if (!(e == 0 && f == 0.0))" part.

It feels like the patch is approaching an acceptable state; after both of you agree it's there, what do I need to do next?
msg157476 - (view) Author: Andrew Svetlov (asvetlov) * (Python committer) Date: 2012-04-04 13:17
Tests passed, looks good. Code is also looks ok.
Documentation is out-of-date. Patch cannot be applied to struct.rst from default branch.
Compilation generates warning messages on gcc 4.6.1:

/home/andrew/projects/py3k/Modules/_struct.c: In function ‘nu_halffloat’:
/home/andrew/projects/py3k/Modules/_struct.c:489:5: warning: pointer targets in passing argument 1 of ‘_PyFloat_Unpack2’ differ in signedness [-Wpointer-sign]
Include/floatobject.h:108:20: note: expected ‘const unsigned char *’ but argument is of type ‘const char *’
/home/andrew/projects/py3k/Modules/_struct.c: In function ‘np_halffloat’:
/home/andrew/projects/py3k/Modules/_struct.c:712:5: warning: pointer targets in passing argument 2 of ‘_PyFloat_Pack2’ differ in signedness [-Wpointer-sign]
Include/floatobject.h:87:17: note: expected ‘unsigned char *’ but argument is of type ‘char *’

After fixing warnings and structure.rst I like to see that patch in standard library.
msg157484 - (view) Author: Antoine Pitrou (pitrou) * (Python committer) Date: 2012-04-04 15:02
Given than there is no native "half float" in C (AFAIK), does it make sense to have a native variant of half floats?
Also:

+    {'e',       sizeof(short),  SHORT_ALIGN,    nu_halffloat,   np_halffloat},

Shouldn't it be 2 rather than sizeof(short)? And why SHORT_ALIGN?

Other comments:
- in the tests, please remove the commented out print() calls
- in the tests, I don't understand why some examples are commented out; you should explain why (add a comment)
- you can add the "import math" at the top-level, rather than in the test method
- in the doc, you need a "versionchanged" or "versionadded" tag to specify that half-float support was added in 3.3

I'll let others review the numerical code, if necessary.
msg157488 - (view) Author: Andrew Svetlov (asvetlov) * (Python committer) Date: 2012-04-04 15:17
I used half-float in GPU programming and from my perspective it was just native. There are no half-float in C, right. But there are half-floats used in NVIDIA libraries for example and I like to think used format is native and platform-depended in general. Correct me if I'm mistaking.
msg157490 - (view) Author: Antoine Pitrou (pitrou) * (Python committer) Date: 2012-04-04 15:25
> I used half-float in GPU programming and from my perspective it was
> just native. There are no half-float in C, right. But there are
> half-floats used in NVIDIA libraries for example and I like to think
> used format is native and platform-depended in general. Correct me if
> I'm mistaking.

By "native", the struct module means there is a corresponding C type and
therefore corresponding rules for size and alignment, as implemented by
the C compiler. GPU structure layout is another matter, as the C
compiler doesn't target that (not in a standard setup, anyway).

Apparently the patch takes the stance that the corresponding C type (for
size and alignment) is "short", which I guess is an acceptable
compromise, but still a bit weird.
msg157491 - (view) Author: Andrew Svetlov (asvetlov) * (Python committer) Date: 2012-04-04 15:32
Antoine, agree with you after explanation.
msg187590 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2013-04-22 20:16
I'll take a look at the numerics.
msg187592 - (view) Author: Paul Hoffman (paulehoffman) Date: 2013-04-22 20:22
Just another voice for seeing this put in a deployed version of Python. Half-precision floats are becoming more common in applications.

Question: does adding this affect math.isnan and math.isinf?
msg187615 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2013-04-23 07:19
I don't see how math.isnan or math.isinf would be affected: we're not proposing to make a float16 Python type, so math.isnan would never encounter a float16 value.
msg187656 - (view) Author: Paul Hoffman (paulehoffman) Date: 2013-04-23 16:23
Mark:

>I don't see how math.isnan or math.isinf would be affected: we're not proposing to make a float16 Python type, so math.isnan would never encounter a float16 value.

I was assuming that this proposal would also make this part of class 'float' just like the other floats returned from struct. Otherwise, you will get goofy cases where someone has to special-case what they get from struct.

import math, struct
FullInfinityAsInt = 0x7f800000
ThisFloat = (struct.unpack("f", struct.pack("I", FullInfinityAsInt)))[0]
print("The type is " + str(type(ThisFloat)))
if math.isinf(ThisFloat):
	print("This is an infiniity")
else:
	print("This is not an infinity")

This should work similarly for the new half-precision, I would think.
msg187658 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2013-04-23 17:27
Paul: your example works because struct.unpack('f', packed_stuff)[0] returns a regular Python float, backed by C double---i.e., exactly the same type that's returned by struct.unpack('d', packed_stuff)[0].  In effect, the single-precision C value is computed and then converted to a double-precision C value (a lossless conversion) before being wrapped in a Python float as usual.  There's no dedicated float32 type, and math.isnan and math.isinf don't have to be aware of anything other than normal Python floats.  float16 packing and unpacking would work the same way: on packing, a Python float would be converted to the closest float16 value and then serialised to a pair of bytes; on unpacking, that pair of bytes is (at least conceptually) converted to a float16 value and then to the corresponding float64 value, wrapped up in a Python float.
msg187661 - (view) Author: Paul Hoffman (paulehoffman) Date: 2013-04-23 17:41
I *think* what you are saying is that there will be no float16 type, but the result of struct.unpack('eorwhatever', packed_stuff)[0] will be the same as struct.unpack('f', packed_stuff)[0], yes? If so, that's what I wanted. I don't want a new float16; I want the output of unpacking a half-precision to be the same as unpacking the other two.

I didn't see a statement like that earlier in the thread, but I could have missed it. Or maybe this was covered in msg132976?
msg188504 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2013-05-06 11:02
Refreshed patch, with a few minor updates:

 - Use copysign instead of signbit (we don't currently check for signbit
   in the configure scripts); only check for negative zero when we've
   already checked equality with 0.0.

 - Use Py_IS_NAN and Py_IS_INFINITY instead of isinf and isnan.

 - Add an extra check for really tiny numbers in _PyFloat_Pack2 to avoid binary64 subnormals in intermediate calculations.

 - Remove a duplicate check for the case x == 0.0 in _PyFloat_Pack2.

 - Make unpacking of ints and nans behave in the same way as float("inf") or float("nan"): use _Py_dg_infinity and _Py_dg_stdnan if available, else fall back to Py_HUGE_VAL and Py_NAN.

 - Minor style nits (braces; use floating-point constants when comparing with floats; consistent capitalization for hex literals, etc.)
History
Date User Action Args
2013-05-06 11:02:17mark.dickinsonsetfiles: + cpython-struct-float16-v6.patch

messages: + msg188504
2013-04-23 17:41:25paulehoffmansetmessages: + msg187661
2013-04-23 17:27:15mark.dickinsonsetmessages: + msg187658
2013-04-23 16:23:52paulehoffmansetmessages: + msg187656
2013-04-23 07:19:41mark.dickinsonsetmessages: + msg187615
2013-04-22 20:22:04paulehoffmansetnosy: + paulehoffman
messages: + msg187592
2013-04-22 20:16:02mark.dickinsonsetassignee: mark.dickinson
messages: + msg187590
2012-04-04 15:32:26asvetlovsetmessages: + msg157491
2012-04-04 15:25:34pitrousetmessages: + msg157490
2012-04-04 15:17:46asvetlovsetmessages: + msg157488
2012-04-04 15:02:42pitrousetmessages: + msg157484
2012-04-04 13:17:28asvetlovsetnosy: + asvetlov
messages: + msg157476
2012-04-03 23:09:07pitrousetnosy: + pitrou

stage: patch review
2011-04-07 16:53:01belopolskysetnosy: + belopolsky
2011-04-05 19:03:26Eli.Stevenssetmessages: + msg133078
2011-04-05 18:32:49mark.wiebesetmessages: + msg133073
2011-04-05 18:08:33Eli.Stevenssetfiles: - cpython-struct-float16-v3.patch
2011-04-05 18:08:27Eli.Stevenssetfiles: - cpython-struct-float16-v1.patch
2011-04-05 18:08:19Eli.Stevenssetfiles: + cpython-struct-float16-v5.patch

messages: + msg133060
2011-04-05 12:23:51mark.dickinsonsetmessages: + msg133025
2011-04-05 12:22:49mark.dickinsonsetmessages: + msg133024
2011-04-05 11:36:53mark.dickinsonsetmessages: + msg133020
2011-04-05 10:10:28Eli.Stevenssetfiles: + cpython-struct-float16-v4.patch

messages: + msg133013
2011-04-05 07:42:41Eli.Stevenssetmessages: + msg133005
2011-04-05 06:53:48Eli.Stevenssetmessages: + msg133004
2011-04-04 22:03:53mark.wiebesetmessages: + msg132980
2011-04-04 21:36:23Eli.Stevenssetmessages: + msg132976
2011-04-04 19:12:32mark.wiebesetmessages: + msg132961
2011-04-04 13:35:23mark.dickinsonsetmessages: + msg132942
2011-04-01 19:40:47Eli.Stevenssetfiles: - cpython-struct-float16-v2.patch
2011-04-01 19:40:40Eli.Stevenssetfiles: + cpython-struct-float16-v3.patch

messages: + msg132765
2011-04-01 19:13:13mark.wiebesetmessages: + msg132764
2011-04-01 19:01:42Eli.Stevenssetfiles: + cpython-struct-float16-v2.patch

messages: + msg132763
2011-04-01 17:16:35Eli.Stevenssetmessages: + msg132761
2011-04-01 07:58:08mark.wiebesetnosy: + mark.wiebe
messages: + msg132732
2011-04-01 07:55:13mark.dickinsonsetnosy: + mark.dickinson
2011-04-01 01:46:56Eli.Stevenssetfiles: + cpython-struct-float16-v1.patch
keywords: + patch
messages: + msg132726
2011-04-01 01:00:15Eli.Stevenscreate