y-cruncher Multi-Precision Library
	A Multi-threaded Multi-Precision Arithmetic Library (Powered by y-cruncher)

(Last updated: March 3, 2016)

 

Known Issues and Possible Improvements:

 

 

Performance:

 

YMP is based off of y-cruncher. And y-cruncher has a long history of optimizing for large sizes and not giving a crap about small numbers and uncommon corner cases.

 

As a result, YMP inherits a lot of inefficiencies from y-cruncher:

• Large multiplication lacks assembly optimized implementations of the Basecase and Karatsuba algorithms.
• There is no special handling of unbalanced products. All multiplications of the same product size will generally run at the same speed.
• Multiplications smaller than ~30,000 bits long are not parallelized even though it may be beneficial to do so.
• The threshold tuning between the various multiplication algorithms is extremely out-of-date.
• Operations like division and radix conversions use only asymptotically fast algorithms which can be very inefficient for small numbers.

In addition to those listed above, there are new inefficiencies which are specific to YMP:

• Memory allocation and page-commit is a huge bottleneck when handling large numbers with RAII objects in a heavily threaded environment.
• Most of the user-friendly RAII objects and functions are not particularly well optimized.

 

 

Exception Handling:

 

YMP's exception handling is currently not great and is in need of an improvement. If both user code and YMP are compiled with the exact same version of Visual Studio, then they will work correctly in all situations except when inside RunInParallel().

 

Otherwise...

Situation	Current Behavior	Desired Behavior
Exception thrown by YMP that propagates to user.	YMP side: Exception caught at the DLL boundary and serialized. User Side: Serialized exception is re-thrown as an std::string.	YMP side: Exception caught at the DLL boundary and serialized. User Side: Exception is deserialized into the original type and rethrown.
Exception thrown by user that propagates to YMP.	Undefined Behavior	User Side: Exception caught at the DLL boundary and serialized. YMP side: Exception is passed up in serialized form and eventually passed back to the user. User Side: Exception is deserialized into the original type and rethrown.
Exception thrown by YMP inside RunInParallel().	Program terminates	Exception is stored until the tasks join. Then it is rethrown.
Exception thrown by user inside RunInParallel().	Undefined Behavior	User Side: Exception caught at the DLL boundary and serialized. YMP side: Serialized exception is stored until the tasks join. It is eventually passed back to the user. User Side: Exception is deserialized into the original type and rethrown.
Multiple exceptions thrown by concurrent YMP tasks inside RunInParallel().	Program terminates	Undecided
Multiple exceptions thrown by concurrent user tasks inside RunInParallel().	Undefined Behavior	Undecided

Aside from these, the existing set of exception classes used by YMP needs to be completely thrown away and replaced with something better. Likewise, there are numerous "terminate on error" calls deep inside y-cruncher/YMP which are leftover from the C99 days. These need to be converted to C++ exceptions.

 

 

Global Twiddle-Factor/Lookup Table:

 

Everything that does large multiplication needs the lookup table. And the global lookup table starts at size 0. Currently, the user is responsible for setting the table large enough to handle all operations. Otherwise, YMP will either crash or throw an exception.

 

Ideally, this global table should automatically resize. But this is tricky because:

1. The resizing needs to be thread-safe with concurrent threads that are using the table.
2. There needs to be minimal run-time performance penalty when no resizing is needed.

Since large multiplication is used "literally everywhere", locking is not going to be scalable - as is often the case with singletons in a threaded environment. One solution is to do something similar to multi-threaded memory allocators. Small multiplications use a fixed sized table. Large multiplications can lock on a larger resizable table.

 

A more scalable solution would be to have multiple independently resizing tables possibly in thread-local storage. But this has two major drawbacks:

1. Higher memory usage. The table is duplicated into every thread (or every NUMA node if you're willing to get fancy).
2. This will need to coordinate with the parallel computing framework so that each framework thread knows which table to use.

 

Other cacheables such as the mathematical constants have similar problems but to a much less extent since they are not accessed that often. Currently, nothing in YMP needs to cache constants, but this will change if support is added for elementary and trigonometric functions.