2009/12/21 Bill Hart <goodwillh...@googlemail.com>: > 2009/12/21 Dan Grayson <d...@math.uiuc.edu>: >> Right. The proposal would be to declare that a bug. Then we would >> have to fix it. Fixing it would mean rewriting mpn_lshift so it >> crashes or returns the right answer with misaligned limbs. If it had >> been written that way in the first place, we wouldn't be having this >> discussion, because I would have seen a misalignment crash instead of >> a wrong answer. >> >> Here's one possible fix that has just occurred to me. Another poster >> suggested that the purpose of the instruction "and r9,-16" was to take >> a presumed 8-byte aligned address and make it 16-byte aligned. Change >> it to "and r9,-9". That adds 7 to the number, making a mask that >> preserves the bottom three bits and thus any 8-byte misalignment, >> maybe prompting a crash in a later instruction, or maybe making it >> give the right answer if the hardware doesn't mind the misalignment. >
Actually I just realised this was a false example, as the lshift there is done on the whole array, which is presumably aligned. A better example is in the toom multiplication code where large integers are split along limb boundaries into smaller pieces which are then used in various mpn functions. I tried writing a toom algorithm which split along half limb boundaries. The algorithm itself should have been faster, but in practice it slowed down because of the penalty the processor imposes on nonaligned memory access. So I had to abandon this approach. > I'm not opposed to making this change. However, I think it would be > misleading for us, having made this change to then certify that MPIR > accepts any alignment. > >> >> By the way, could mpir be written to be faster if memory allocators >> all returned 16-byte aligned data? It seems to be the case for this >> routine. > > I believe that to be the case. However, whilst Windows memory > allocators probably operate this way, I am not sure that all *nix ones > do. I think it would be a bug to make this assumption. > > Of course in practice MPIR operates on arrays of limbs. If functions > assumed all such arrays were 16 byte aligned then a vast number of > functions would break. For example the FFT code likes to do an > arbitrary shift by 2^d mod 2^aN + 1 by first shifting by an integral > number of limbs, then shifting by an amount which is less than a limb. > The second part of this only assumes limb alignment, not double limb > alignment at present, so the code would be broken if the lshift > function assumed the latter. > > So whilst MPIR could be written to be faster if this assumption was > made, it would be a big job. It's also not clear to me what the > interaction with the C compiler would be. Some of its optimisations > may only assume limb alignment and thus it may do invalid > optimisations. I cannot think of such an example, and perhaps this > wouldn't be an issue in practice. But MPIR already hits many compiler > bugs as it is, so I wouldn't tempt fate. > > Bill. > >> >> On Dec 20, 2:50 pm, Bill Hart <goodwillh...@googlemail.com> wrote: >>> 2009/12/20 Dan Grayson <d...@math.uiuc.edu>: >> ... >>> > What about installing a test under "make check" that tries all >>> > routines with misaligned limbs? Let the misalignment vary. Declare a >>> > routine to "pass" if it gives the correct answer or crashes or aborts >>> > the program. Declare the routine to "fail" if it gives an incorrect >>> > answer. That would have caught the lshift routine I reported. There >>> > might be some discussion about whether that behavior of mpn_lshift >>> > counts as a bug. >>> >>> I'm not sure I completely understand. We already know that lshift will >>> return the wrong answer if the limbs are unaligned (as your example >>> demonstrated). It isn't designed to work with unaligned limbs. >> >> -- >> >> You received this message because you are subscribed to the Google Groups >> "mpir-devel" group. >> To post to this group, send email to mpir-de...@googlegroups.com. >> To unsubscribe from this group, send email to >> mpir-devel+unsubscr...@googlegroups.com. >> For more options, visit this group at >> http://groups.google.com/group/mpir-devel?hl=en. >> >> >> > -- You received this message because you are subscribed to the Google Groups "mpir-devel" group. To post to this group, send email to mpir-de...@googlegroups.com. To unsubscribe from this group, send email to mpir-devel+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/mpir-devel?hl=en.
