On 23/12/2010, at 11:36 PM, Johan Corveleyn wrote:
> On Thu, Dec 23, 2010 at 3:44 AM, Gavin Beau Baumanis
> <gavinb_at_thespidernet.com> wrote:
>> Hi Johan,
>
> Hi Gavin. Thanks for your interest. It's a nice problem isn't it?
Yes - it "should be" so very simple... but a little thought - and before you know it - it's not!
>
>> I was intrigued by your requirement to create a large file for testing.
>> I remember from a really long time ago when I learnt C, that we used a specific algorithm for creating "natural" and "random" text.
>> With some help from Mr.Google found out about Markov Chains that look promising - I can't remember if that was what I learned about or not - but it looks like it might be a prove helpful none the less.
>>
>> A little further Googlng and I found this specific post on stackoverflow.
>> http://stackoverflow.com/questions/1037719/how-can-i-quickly-create-large-1gb-textbinary-files-with-natural-content
>
> Interesting link. If I'm reading it correctly, the best suggestion in
> there was with those Markov Chains. But it seems maybe a little
> overkill / too much work for me.
I might have an answer for you there.
I pointed out this thread to our intern.
He seems to know about Marchov chains already - I have asked him to contribute to the thread.
>
>> No Idea if it is going to help you specifically or not... but there are quite a few ideas in the comments;
>> * Obtain a copy of the first 100MB from wikipedia - for example.
>
> Nah, I wouldn't like to depend on some internet resource.
>
>> Finally, if you happen to a large enough file already, could you not use "split" (unix) function to give you a specific sized file?
>
> Yes, but we'll first need that large enough file :-).
>
>>
>> Actually - I was so intrigued by the "challenge" of this - I have had a think of it over lunch;
>>
>> Could you not do this?
>> (pseudo -code)
>>
>> Start with a known "chunk" - say the license file.
>> get length of license file - for example only = 125bytes
>> append the chunk to itself until such time as you have the required size.
>> write the file once.
>>
>> startSize = length(knownFile);
>> int numberOfLoops = log2(desiredFileSize / knownFile) ;
>> newFile = knownFile
>>
>> Loop for numberOfLoops
>> {
>> newFile = newFile +newFile
>> }
>>
>> write newFile;
>
> Yes, that certainly seems a sensible approach. I actually had the same
> idea (see below, "doubling the file until I have enough (cat file.txt
>>> file.txt)). Well, it's almost the same: in your suggestion the file
> is built up completely in memory and only written out in the end.
> That's also an option, but I think it's better to write it out every
> time it's doubled (to avoid using up too much memory).
I certainly understand that, But in todays GB RAM PCs / Laptops;
Is a 100 MB file in memory such a worrisome issue?
It would only be short lived - until the file was written out. The memory could then be cleared?
And from your first email - it seemed like timing was the hurdle to clear and file open / write / close every iteration of the loop could certainly be the bottleneck of your first attempt.
Anyway - Please be sure not to let me "bully" you into anything you don;t think is right for your requirements :)
Andy (our intern) might be able to provide the missing link for you.
none the less, Good Luck.
<snip>
>
> But good suggestion anyway. I think I will go with some variation of
> this (starting with a large enough chunk of representative content).
>
> Cheers,
> Johan
>
>> On 23/12/2010, at 11:51 AM, Johan Corveleyn wrote:
>>
>>> On Wed, Dec 22, 2010 at 11:50 AM, Philip Martin
>>> <philip.martin_at_wandisco.com> wrote:
>>>> Johan Corveleyn <jcorvel_at_gmail.com> writes:
>>>>
>>>>> On Mon, Dec 20, 2010 at 11:19 AM, Philip Martin
>>>>> <philip.martin_at_wandisco.com> wrote:
>>>>>> Johan Corveleyn <jcorvel_at_gmail.com> writes:
>>>>>>
>>>>>>> This makes the diff algorithm another 10% - 15%
>>>>>>> faster (granted, this was measured with my "extreme" testcase of a 1,5
>>>>>>> Mb file (60000 lines), of which most lines are identical
>>>>>>> prefix/suffix).
>>>>>>
>>>>>> Can you provide a test script? Or decribe the test more fully, please.
>>>>>
>>>>> Hmm, it's not easy to come up with a test script to test this "from
>>>>> scratch" (unless with testing diff directly, see below). I test it
>>>>> with a repository (a dump/load of an old version of our production
>>>>> repository) which contains this 60000 line xml file (1,5 Mb) with 2272
>>>>> revisions.
>>>>>
>>>>> I run blame on this file, over svnserve protocol on localhost (server
>>>>> running on same machine), with an svnserve built from Stefan^2's
>>>>> performance branch (with membuffer caching of full-texts, so server
>>>>> I/O is not the bottleneck). This gives me an easy way to call 2272
>>>>> times diff on this file, and measure it (with the help of some
>>>>> instrumentation code in blame.c, see attachment). And it's
>>>>> incidentally the actual use case I first started out wanting to
>>>>> optimize (blame for large files with many revisions).
>>>>
>>>> Testing with real-world data is important, perhaps even more important
>>>> than artificial test data, but some test data would be useful. If you
>>>> were to write a script to generate two test files of size 100MB, say,
>>>> then you could use the tools/diff/diff utility to run Subversion diff on
>>>> those two files. Or tools/diff/diff3 if it's a 3-way diff that matters.
>>>> The first run might involve disk IO, but on most machines the OS should
>>>> be able to cache the files and subsequent hot-cache runs should be a
>>>> good way to profile the diff code, assumming it is CPU limited.
>>>
>>> Yes, that's a good idea. I'll try to spend some time on that. But I'm
>>> wondering about a good way to write such a script.
>>>
>>> I'd like the script to generate large files quickly, and with content
>>> that's not totally random, but also not 1000000 times the exact same
>>> line (either of those are not going to be representative for real
>>> world data, might hit some edge behavior of the diff algorithm).
>>> (maybe totally random is fine, but is there an easy/fast way to
>>> generate this?)
>>>
>>> As a first attempt, I quickly hacked up a small shell script, writing
>>> out lines in a for loop, one by one, with a fixed string together with
>>> the line number (index of the iteration). But that's too slow (10000
>>> lines of 70 bytes, i.e. 700Kb, is already taking 14 seconds).
>>>
>>> Maybe I can start with 10 or 20 different lines (or generate 100 in a
>>> for loop), and then start doubling that until I have enough (cat
>>> file.txt >> file.txt). That will probably be faster. And it might be
>>> "real-worldish" enough (a single source file also contains many
>>> identical lines, e.g. all lines with a single brace etc.).
>>>
>>> Other ideas? Maybe there is already something like this lying around?
>>>
>>> Another question: a shell script might not be good, because not
>>> portable (and not fast)? Should I use python for this? Maybe the
>>> "write line by line with a line number in a for loop" would be a lot
>>> faster in Python? I don't know a lot of python, but it might be a good
>>> opportunity to learn some ...
>>>
>>> Are there any examples of such "manual test scripts" in svn? So I
>>> could have a look at the style, coding habits, ... maybe borrow some
>>> boilerplate code?
>>>
>>> Cheers,
>>> --
>>> Johan
>>
>>
Received on 2010-12-23 23:44:01 CET