On 3/4/2011 6:29 AM, Chad Nelson wrote:
On Fri, 04 Mar 2011 01:18:53 -0800 "Jeffrey Lee Hellrung, Jr."<jhellrung@ucla.edu> wrote:
It's rather late to make huge changes to the library at this point.
I shouldn't think so. Do you feel this way because the library is currently under review?
I feel this way because I'm at the end of both my patience and my freedom to devote months on end to something that isn't paying work. I spent five months of twelve- to fifteen-hour days on it last year, first writing it and then *rewriting* it six more times, trying to satisfy the people on this list. When I asked for comments on the seventh iteration, I got dead silence, which I took to mean that I'd sufficiently satisfied everyone's desires. Obviously not.
I can probably speak for most everyone that we certainly appreciate the time you've put into this to get an actual, concrete bigint proposal that we can have a serious dialogue about. At the very least, it's brought out what others hope to see in a bigint library. Regarding the feedback from previous versions, you should understand that two major (to me, at least) suggestions from previous versions were: - Eliminate COW entirely, or, at the very least, don't make it mandatory. Add it on top of an existing, public infrastructure, if you really want. And if it is used, I think it would be most appropriate for an immutable data structure. As far as I can gather from your past comments, COW is still being used internally. Yes, this is largely an implementation concern, but I think a valid concern nonetheless. - Separate the arithmetic algorithms from the data structures, defining a BigInt concept or group of concepts in the process. Regarding the former, it appears we still don't have a definitive benchmark comparing COW with move emulation, and one would be nice, but we can still predict how many deep copies each strategy will require for a given expression, and except in constrained situations where copies are never modified, I don't think COW gives any benefit. Sometimes COW is worse, since you can't explicitly transfer ownership. Feel free to prove me wrong. If you can give an example we can analyze where COW performs fewer copies, it would help your cause. For example: integer x = ..., integer a = ..., integer b = ...; x = a + b; In both cases, there should should be a single allocation to hold the temporary sum a + b, which subsequently gets transferred to x. Regarding the lack of feedback on your *seventh* iteration, it's unfortunate, but I think, throughout your development process, that it was reasonable to expect: - that not everyone is going to inspect every iteration of your library; and - that you will get (by far?) the most of amount of feedback (including critical, almost negative, feedback) on the version you submit for inclusion in boost.
If the library is accepted or conditionally accepted, I'll be happy to continue improving it in my spare time, and probably even redesign it based on the suggestions I've gotten. If it is outright rejected, it dies. I'm not completely rewriting it yet again in a vain attempt to satisfy people who will never be happy with it.
Rewriting the library for the primary purpose of satisfying the boost development list is the wrong perspective to take. If you don't view the majority of the suggested modifications as positive directions to take your library in, then maybe boost is the wrong destination for xint. For what it's worth, I will vote to not accept, but I will try to summarize my reasons for doing so in a separate email.
Ummm...yes, the stated complexity is correct, but O(n(n+1)/2) = O(n^2).
So asymptotically speaking, it's not any faster than using the naive grade-school multiplication algorithm. Like I said, unless you want to give a precise operation count, it's just O(n^2).
Um... if you plug a concrete number into both equations, the answers are quite different.
Um... I'm not really sure how to respond to this. It's not a huge deal as far as the documentation is concerned, but if you *really* think that O(n^2) and O(n*(n+1)/2) are different guys, then I don't have a lot of confidence in the rest of your (as-yet-unchecked) complexity claims...
I have no formal training on big-O notation, only what knowledge I've managed to pick up over the years of trying to interpret discussions of programming algorithms. If half of roughly n^2 is somehow considered equal to n^2 in big-O notation, then obviously that isn't sufficient.
I think a quick trip to wikipedia, as suggested by Robert, should convince you. Complexity theory is certainly a valuable tool for any programmer to have, so I'd suggest getting up to speed as soon as convenient. wikipedia articles should be sufficient.
I added the complexity estimates because someone on this list said that the library had to have them. Without volunteering to do any of the considerable work, I might point out. I tracked down the estimates from real mathematicians when they were available; when they weren't, I had to make educated guesses based on what I knew. Some of them will inevitably be wrong, that's the nature of the beast.
Fair enough. Like I said, I suggest familiarizing yourself with the concepts then. [...]
Besides, COW isn't on by default...
It's used internally regardless, as I control everything within the library and can ensure that it's used safely. The thread-safe option only prevents it for integers returned to the user.
Whoa, wait a second here. I can't help but see a red flag here, so color me incredulous and possibly very naive. How can copy-on-write help you internally where just moving the internal data isn't possible? Can you give an example of the internals where you find copy-on-write necessary?
Only the benchmarks that I came up with before, and referred you to earlier in this thread. They may well change when I correct the pass-by-value stuff.
Sorry if this wasn't clear, so let me rephrase. Which implementation function or block of code necessitates using COW to eliminate unnecessary copying? This doesn't require benchmarking, only code analysis.
I had a publicly-available make_unique function in an earlier iteration of the library, and was criticized for it, so I removed it. I don't remember if it was you personally doing the criticizing, but you-the-Boost-community can't have it both ways. :-)
Well this tagged copy constructor pretty much amounts to the same thing, doesn't it? Only less efficient, since it will actually perform a deep copy in situations where it's not needed, e.g., when the object is already in the thread you want it to be owned in.
Only if the person is foolish enough to explicitly tell the library to do so. I'd like to think that any programmer using the library wouldn't be that foolish.
You didn't really address my primary comment. You can put lipstick on a pig, but it's still a pig. You've just renamed make_unique into a constructor. Is that a fair analysis?
And more cryptic in client code. By the way, is there ever any reason to set the boolean force_thread_safety to false?
It should essentially *always* be false, that's why false is the default value. Either thread-safety is already on for the type that you're using (the default, by the way), in which case setting it to true is redundant, or it's off for that type, in which case you must have explicitly told the library that you're only using objects of its type in a single thread and will assume responsibility for any changes to that plan. That parameter exists solely so that, *if* you've told the library that you're only using it in a single thread, you can override that for specific copies of integer objects that must cross thread boundaries.
Sorry, is there any reason to set the boolean force_thread_safety *explicitly* to false? I suspect the answer is "no", so I would consider this an inferior design to just have the regular copy constructor augmented with another constructor that takes a special empty tag struct whose only purpose to ensure the copy has unique storage. But ultimately it's a moot point as it's just a hack to obscure the make_unique member function into something else, and make_unique would be preferable still. And even *that* is somewhat of a moot point as I don't think COW should be used for the base integer class in the first place :/ - Jeff