Jump to content

Jud

Members
  • Content Count

    118
  • Joined

  • Last visited

Everything posted by Jud

  1. Jud

    Maximum static memory

    I could extract the relevant code and give a real data set, but it would take some work and the data would be very large. But several days ago I abandoned the bucket sort method and now the quicksort method is working and producing results. I think the problem was because there are millions of buckets and almost all of them are empty, so there is a lot of work with memory. (Actually, on two small test cases, the bucket sort system was 30% and 3X faster than the quicksort version, but on big data sets, there are way too many buckets, almost all empty.) Also, I can multithread the version that uses quicksort. I wouldn't be able to do that effectively with the bucket sort system because of the large memory. (The workstations here have 128GB of RAM, and one instance was taking up nearly half of it.) --------------- A few years ago when I had a large dynamic array of short tLists, it seemed that it was reserving 4KB for each list, even if the list was much smaller. Is that how the memory manager works?
  2. Jud

    Maximum static memory

    I thought the minimum was 4KB. So if I have a dynamic array with the SetLength to 1000 bytes, it is actually going to allocate 64KB? I could rig up a small demo, with real data in a couple of hours, but I think that the problem is with bucket sort, it turns out that almost all of the buckets are empty (I couldn't tell this until I got it working and collected some statistics). A secondary cause could be that I have a static array of counters to tell how many items are in each bucket, and I use FillChar to zero out in each of the 143,000,000 calls to the procedure. That array has about 60,000,000 bytes, but I only zero out as much as I need to, which varies with each call to the subroutine.
  3. Jud

    Maximum static memory

    I don't know if anyone is still reading this, but I got the bucket sort method working. On small cases, it is up to 3 times faster than the quicksort method. But on data sets that are of interest, it is much slower. On a test case with real data, the quicksort method takes 61 minutes but the bucket sort method takes 27 hours. The procedure that does the work doesn't know how many buckets there will be or how large they will need to be until it gets the data. For that reason, I used a dynamic array of dynamic arrays, outside the procedure. I did some statistics on the test case (that has real data). The procedure is called about 143,000,000 times. There are up to about 26,000,000 buckets. However, there are at most about 5,400 items spread out in those buckets. So about 99.98% of the buckets are empty. That is the reason it is so much slower than quicksort - going through all of those empty buckets. The bucket sort was potentially a good idea, but it didn't turn out well. I wasted a lot of time on it, but I learned some things.
  4. Jud

    Maximum static memory

    No, it depends on what the rest of the program is doing. An O(n log n) quicksort could take 99%+ of the time, depending. I've been using quicksort for over 40 years and I tested it on this data.
  5. Jud

    Maximum static memory

    It is late and I'm about to be away for a couple of days. I haven't finished all of the changes I talked about (with fewer but bigger buckets) but it definitely seems that the problem is in swapping out the very large dynamic array to the drive millions and millions of times. Details by the middle of next week.
  6. Jud

    Maximum static memory

    Well, I think I have figured it out. I think the memory manager is allocating memory for the dynamic arrays in 4KB chunks, no matter how much is needed. That is causing it to swap to the SATA SSD like crazy. I develop on a computer that has 32GB. I have it show me how much memory is available after I SetLength, and it says about 19GB left. I took the very same EXE and ran it on a computer with only 16GB. It should use up all of the memory, but it was showing about 9GB available. So it has to be swapping out. In the old days, I would have hard the hard drive accesses. In Task Manager, it does NOT show the drive activity, but the system must be doing it, I think (otherwise there is no way it would run at all on the 16GB machine). If it is allocating minimum chunks of 4KB, as I think, the total memory use is approaching 200GB. Which brings be back to the original Delphi philosophy of "you'll never need more than 2GB, even in 64-bit programs". But I've thought of some work-arounds. Primarily, reduce the number of buckets by a factor of, say, 256. Then anything that would have gone into buckets 1-256 go into the first bucket, 257-512 go into the second bucket, etc. That will make efficient use of the 4K blocks. Then a little processing on each of these bigger buckets will get it ready for the final processing stage.
  7. Jud

    Maximum static memory

    I think the problem is probably calling SetLength on a fairly large dynamic array millions of times inside a procedure is overwhelming the memory manager. I need to keep a count showing how many times it has been called in the last second, and see if that starts to drop. Maybe I can get some sample code. I'm trying different things. Today I finished a run after making the 2-dimensional non-rectangular array global, so SetLength isn't called for it millions of time inside the procedure that prepares the data for the final phase. This was faster, but the run took 39.6 hours, as opposed to about 2.2 for the quicksort approach. But I have a dynamic array inside that procedure that tells me how many elements across the big array is. I gathered some statistics during the run and it shows that this array could be less than 200 megabytes, so I'm going to try making it a global static array. Inside the procedure that is called millions of times, I have to set part of the array to zero, but I know how much of that array needs to use FillChar.
  8. Jud

    Maximum static memory

    The final phase of the processing needs the items in buckets, so bucket sort seems logical. It should beat quicksort. I think the problem making it slow was that the procedure that prepares the data for final processing is called millions of times and the large dynamic array of arrays was inside that procedure, calling SetLength each time. I've just made the large dynamic array global and SetLength to once to reasonable estimates, and then increase it if necessary. That is working but I haven't compared it to quicksort yet.
  9. Jud

    Maximum static memory

    I'm hot shuffling the records, I'm grouping them according to how they are to be processed. The records are 16-bytes long (there are a lot of them). Yesterday (after watching a Webinar and installing Delphi 11.0, yes it is available) I did more profiling. I said that the quicksort was taking 80%. There is a SwapRecords procedure nested in the quicksort procedure that is taking an additional 7%. I went back to my earlier version (with compiler directives) - the one that uses a non-rectulangular dynamic array of dynamic arrays. The profile shows that SetLength is taking most of the time. The profiler shows "system" using 77% of the time. @FillChar is using the most, which must be zeroing out the dynamic array (which ( don't need). SysGetMem is second in the profiler. But yesterday I had the idea of using a large dynamic array of small static arrays. I think that is going to work (in 64-bit mode). Also, what Administrators said above just made me think of another possible approach. Keep the dynamic array of records and go through and pick out the ones with a certain key, and process them. Repeat with the next key. The problem with this is that there are so many keys (and each one will have to make a pass through the array) that I think it will be back to quadratic time. Probably tomorrow I will implement the dynamic array of small static array method.
  10. Jud

    Maximum static memory

    I've installed that. It gives me the message "Neither TD32, MAP, nor JDB information were found...". EDIT: I found where to turn on the MAP file, and I think it is working. Results: it is spending 80% of its time in Quicksort. So I need to go back to trying the bucket sort.
  11. Jud

    Maximum static memory

    What is a good low-cost profiler? I downloaded AQtime but its trial period is short, then it is expensive.
  12. Jud

    Maximum static memory

    I haven't gotten back to that yet, but I'm going to do timings and see.
  13. Jud

    Maximum static memory

    I think the problem may have to be with the data allocation, since bucket sort (the natural thing for this data) is so much slower than quadratic-time brute force. But I need to get back to looking at it - I've taken a different approach for now and I got the first working version going yesterday, The procedure that puts the data in buckets is called millions of times, with data arrays of varying sizes, but the bulk of them under 100. I switched to doing a quicksort and it took 6.8 hours on the test case, as opposed to 17.7 hours before. So a lot of the time is not in this procedure now, so I don't know how much faster a linear-time sort would be. Since so many calls to the procedure have a small number of records, I compared several sorting methods to quicksort on different sizes of data. Quicksort beat them all until the size got down into the 20s - then selection sort started outperforming quicksort by a good margin. An interesting thing - I was testing several sorts, and I've read many times that insertion sort is the fastest of the quadratic-time sorting algorithms. But, on these data records, selection sort beat insertion sort significantly. I'm going to get back to looking at the original bucket method.
  14. Jud

    Maximum static memory

    I need to update (I've been away for a couple of days). Here is the situation. A program does a lot of processing and calls a procedure to do the final work. This procedure is given an array of records, which can number in the millions. The procedure is called a large number of times. The procedure does some work matching pairs of records that meet certain criteria. At first, I just did a brute-force quadratic time pair of nested loops, to make sure it was working. (Get it right before making it fast.) The test run took 17.7 hours. I knew there were better ways to do it. The obvious choice is to do a bucket sort on the data before processing it. A static array is limited to something less than 2 billion bytes, as far as I know. This isn't enough, so I tried a tw0-dimensional non-rectangular array for the bucket sort. (The first dimension is potentially in the millions, or many millions, but the size of each bucket is small.) I thought this would be much faster than the quadratic-time brute-force method, but it ran for 2 days on the test case and didn't get anywhere near finishing. I think part of the problem is that I'm using SetLength on the daynamic array of array a lot of times inside the procedure. I might can avoid that, but I haven't tested it yet. Right now I'm working on a quicksort of the data, even though a bucket sort is theoretically faster. I have it working on small cases, but later today I should have it working on the test case. So that is the background and where I am.
  15. Jud

    Maximum static memory

    By static, I mean an array that is not a dynamic array. Briefly, hat the program needs to do would naturally use a two-dimensional non-rectangular dynamic array. The array would have millions of rows, but each row would be a short list. I wrote it that way, but performance is terrible. The sizes aren't known until the procedure is run. I believe memory is allocated in 4KB blocks (and zeroed out), which is a lot more than each row needs. I think this is the bottleneck. added... I thought of something else to try - set the length of the dynamic array of arrays once, outside the procedure and enlarge as necessary. That may work if it doesn't use up too much memory.
  16. Jud

    Maximum static memory

    It is on a 64-bit system. I tried both the 32-bit and 64-bit platforms in Delphi.
  17. I don't know what LSP is, but thanks.
  18. I do NOT have DevExpress units in uses.
  19. Yes, I applied the two patches to 10.4.2 earlier this week. Find Declaration is now working for me. Refactor/rename is not working at all.
  20. I haven't had any problems with Find Declaration since I got 10.4.2 (I had problems with earlier versions. But Refactor/Rename is still not working at all.
  21. Yes. I don't know why or when it happens. I don't think I ever had the problem with 10.3, which is why I still also have 10.3 on my desktop. When the 10.4.x IDE isn't working, I have to go back to 10.3. Of the 10.4 versions, if I recall correctly, 10.4.1 BEFORE the patches worked well.
  22. And I can't log in to the quality website. It won't take the password I think I used and it doesn't give me the option of resetting it. It says " If you think this message is wrong, please contact your JIRA administrators. " but I have no idea what JIRA is.
  23. For me, it comes and goes. Today it is working again. When I had the problem I tried rebooting, etc, and nothing I did fixed the problem. It just started working again. Also, I got 10.4.2 shortly after it came out, and putting the cursor over a variable to see its contents wasn't working, although ctrl-F7 was. But yesterday it started working.
  24. I've had problems with it, off and on, for the last few versions. Seems like sometimes a build would fix it. Sometimes going to another project and back would fix it. But tonight it stopped working for me completely and nothing I tried (including deleting the DSK file) would fix it.
  25. I've written several multi-threaded programs with the parallel library, usually using tasks but one or two using parallel for. I have a new one that is more natural for parallel for. The problem is that this is the first one that must use recursion. Inside the loop there is some initial stuff and then it calls a procedure that calls itself, and that isn't working. If the parallel loop only has one iteration, e.g. parallel.for(1,1 ... ) or parallel.for(2,2 ... ), it works. But for actual work, with the recursion and parallel.for, it locks up. How can I get a recursive procedure to work in a multi-threaded program?
×