Jump to content

Leaderboard


Popular Content

Showing content with the highest reputation on 02/24/20 in all areas

  1. I have never liked the idea of a hash, and I use an implementation of a ternary seach tree as a dictionary. I based it on an article in Dr Dobb's Journal in 1998, and it has stood the test of time! I have versions for C and Pascal; the latter for AnsiChar, WidwChar 32-bit and WideChar 64-bit keys. It is incredibly fast and easy to use, and has reasonable memory consumption, unless of course you load a million random 100-byte keys (which takes only a second or so). It has various ways to load and look up keys, and to traverse the set; values can be integer, object or string. I use it it in many different ways, both to match a full key and to find the longest initial partial key. On updating a value, the space used by the old value is not recovered, but that suits most of my uses as a dictionary; and the unit does include a function to rebuild the data store for a dynamic application, if you can spare a second to do so. In its simplest form: tree := tTSTtree.Create; tree.insert(key, value); q := tree.match(key); if (q <> nil) then s := string(pchar(q)); The source is reasonably well commented, and I would be happy let you have a copy, but I have never got around to properly documenting it and uploading it somewhere.
  2. The Delphi world contains a lot of database-solutions. One school of them are the TDataSet-based libraries, components and classes. If you are using TDataSet-based cached Lookups in a more "modern Delphi" you can easily speed up lookup handling. I'm posting this because when i googled in order to fix a couple of thing in my current project, i did not find much, almost nothing on this. This can save HUGE amounts of processor cycles if: You use "VCL Lookups" (they are not strictly VCL, but that is the term for example in DevExpress* forums) and have a lot of value-rows and a lot of lookup values. You use a component that cannot use lookup values and therefore need to "expand" the lookup values with their actual looked up "listfield" value. * I use the DevExpress PivotGrid a lot. The "QuantumGrid" has a "SortByDisplayText" property for sorting on lookup values. But the PivotGrid does not. So for the data fed to a PivotGrid i see to it to use "VCLLookups" so that the PivotGrid handles looked-up values rather than their IDs... as if they where text. This is the only way to get columns/rows sorted the way the users want. In a scenario with 100K rows and 80K lookup values having a character length of 256, this decreased the time needed to load the PivotGrid with data (for each fetch the lookup values is "expanded"). In some scenarios (like the one i describe above) the time needed for the operation (and that is the time the user has to wait) decreased from 120 to 6,5 seconds. The reason being the "LookupCache" in Data.DB uses an O(1) algo on a Variant. Let's change that like so: 1. The treading "lightly" approach is to override you TDataSet-based class, mine is called TkbmMemTable: ... interface ... // Faster lookups TDictionaryLookupList = class(TLookupList) private FDict: TDictionary<Variant, Variant>; public constructor Create; override; destructor Destroy; override; procedure Add(const AKey, AValue: Variant); override; procedure Clear; override; function ValueOfKey(const AKey: Variant): Variant; override; end; TkbmMemTableEx = class(TkbmMemTable) protected function GetLookupListClass(Field: TField): TLookupListClass; override; end; ... implementation ... function TkbmMemTable.GetLookupListClass(Field: TField): TLookupListClass; begin Result := TDictionaryLookupList; end; ... { TDictionaryLookupList } procedure TDictionaryLookupList.Add(const AKey, AValue: Variant); begin if not VarIsNull(AKey) then FDict.Add(AKey, AValue); end; procedure TDictionaryLookupList.Clear; begin FDict.Clear; end; constructor TDictionaryLookupList.Create; begin inherited; FDict := TDictionary<Variant, Variant>.Create; end; destructor TDictionaryLookupList.Destroy; begin if FDict <> nil then Clear; FDict.Free; end; function TDictionaryLookupList.ValueOfKey(const AKey: Variant): Variant; begin if (not VarIsNull(AKey)) and (not FDict.TryGetValue(AKey, Result)) then Result := Null; end; I am NOT "indexing" on Variant here. The TDictionary<Variant, ....> will convert variants to strings because the Dictionarys keys are hashed. I do not think that any database solution will yield a value when the key is null. But please comment if you are aware of such a scenario. 2. The "One Dict to rule them all" approach: Instead of having each flavour of TDataSet kick in the new LookupList you can substitute the vanilla one for our dictionary based one for the entire application: .... initialization DefaultLookupListClass := TDictionaryLookupList; This will see to it that any TDataSet that does not have it's own lookuplist will use the dictionary one. This approach can be tested in almost any application in under an hour. It would be interesting to receive a comment or two if it affected the performance of your application. Please note: This is only useful for lookup fields that have the "LookupCache" flag set. HTH, /Dany Disclaimer one: I did not look at lookups on segmented indices. Disclaimer two: All coding is done under the responsibility of the coder, not the author of this article.
  3. Thijs van Dien

    pre-generic dictionary class

    TStringHash is a completely different class than THashedStringList and gives you exactly what you asked for: string to Integer (Pointer). I've been happily using it in D6 and it's still publicly available in D2010 (the latest version I have at hand). Sure it might not be the absolute optimal solution, but it will be a noticeable improvement over the status quo, is very understandable, and doesn't need any third party code.
  4. Angus Robertson

    pre-generic dictionary class

    ICS includes a unit OverbyteIcsAvlTrees.pas written by Arno Garrels, from the unit: Implements a fast cache-like data storage based on two linked AVL-Trees for primary and secondary indexing. Primary key of type string has to be unique, secondary key of type TDateTime may have duplicates. AVL or balanced binary trees are extremely efficient data structures for searching data. Finding an element in 65536 requires at most 16 compares. Uses an AVL-Tree as it is described in the book "Algorithms & Data Structures", Prof. Niklaus Wirth. No real dependencies on other ICS units. Angus
  5. Uwe Raabe

    MMX for Delphi 10.3 Rio

    Unfortunately the problem is still present. The good thing is, that I now have the environment to investigate it. May take some time though...
  6. A github search revealed these: - https://github.com/coolsoftware/VHashedStringList - https://github.com/bodo-hugo-barwich/hash-lists I didn't take a closer look. Just dumping the links here.
  7. Alexander Sviridenkov

    pre-generic dictionary class

    @dummzeuch written in a unit header - "Free for any use"
  8. David Heffernan

    pre-generic dictionary class

    Expand a generic dictionary implementation manually. Just replace the TKey and TValue textually. It would also be very valid to stop developing GExperts for pre generic delphi.
  9. Knew that was coming 🙂 This is a monumental task because some patches made it into Tokyo and I merged them while another I applied. I can't exactly publish System.Threading which alters some things dramatically. Will attach the RSP-11267 patch since it was applied over the unaltered Berlin Threading unit. Will add my notes so you get an idea of the changes and limitations. Will add the simple changes which alter the constants used. Not sure how I can deal with some of the core changes though.. Tokyo never made it onto my development machine, that merge was simply an easy way to create an intermediate file that should have been used to update Rio. But in Rio System.Threading was altered so that 1.5 years after its original release we still have to deal with posts like this one.. needless to say I never made that merge.. interface {$REGION 'History'} // earlier - Modified as per RSP-11267 // 09-Jan-2019 - Changed MonitorThreadDelay to 100 to be more responsive, if we are taking a clients system // to 95% CPU or higher shouldn't we be able to adjust that without a long pause // - Changed NumCPUUsageSamples to NumCPUUsageSamplesShort (1000ms) and NumCPUAvgSamples (5000ms) // - Changed Retirement Delay to 500ms Idle already can take 80-320 seconds // - Allow Parking/Suspending of unlimited threads, this is key when another application starts to // chew up resources while tasks have already been spawned // - Fixed CPU usage, was turned off after the last Queued task began work // - Fixed a silly timeout patch that should have used the NoWorker flag instead // Be Aware this may not be a perfect solution if more than one pool is created. // An Assertion has been added to highlight this possible issue // 10-Jan-2019 - Added RunningThreadCount // - Calling CreateMonitorThread always now; We want a Singleton MonitorThead regardless of the amount of Tasks requested // - Added Output2Debug function // 20-Jan-2019 - Merged non Tokyo specific changes from Tokyo // - There are Tokyo specific changes that must be done in a new File {$ENDREGION} {$I ..\..\MatchDelphi.inc} {$TYPEDADDRESS OFF} // required for Resource String Pointers {$SCOPEDENUMS ON} {-$DEFINE OUTPUT_DEBUG_STRING} // Activate to show Output2Debug Messages {$IFDEF DEBUG} {$MESSAGE HINT 'Altered System.Threading tested for Single/Default TThreadPool Only'} {$ENDIF} /// <summary-Fred> /// Changed MonitorThreadDelay to 100 to be more responsive, /// if we are taking a clients system to 95% CPU /// or higher shouldn't we be able to adjust that /// </summary> MonitorThreadDelay = 100 {500}; /// <summary-Fred> /// We keep two Averages now, one of 5 secs for standard output as before /// and another for 1 sec used to calculate Suspensions/Parking /// </summary> NumCPUUsageShortSamples = 1000 div MonitorThreadDelay; NumCPUAvgSamples = 5 * NumCPUUsageShortSamples; /// <summary-Fred> /// SuspendInterval is the value used to limit the number of threads that /// can be Parked, IMO this should reflect MonitorThreadDelay because that /// is the time it takes to recalculate the CPU Averages /// </summary> SuspendInterval = MonitorThreadDelay; // Interval to use for suspending work in worker threads /// <summary-Fred> /// Twice MonitorThreadDelay seems to work well /// </summary> SuspendTime = MonitorThreadDelay * 2; // Time to spend in SuspendWork; RetirementDelay = 5000; // Delay interval for retiring threads and finally the output of the original test: Altered Threading Berlin x64: Before: Worker: 0, Min: 4, Max: 100, Idle: 0, Retired: 0, Suspended: 0, CPU(Avg): 0, CPU: 0 After: Worker: 4, Min: 4, Max: 100, Idle: 3, Retired: 0, Suspended: 1, CPU(Avg): 100, CPU: 100 Finished in 00:00:37.3397033 Before: Worker: 4, Min: 4, Max: 100, Idle: 4, Retired: 0, Suspended: 0, CPU(Avg): 7, CPU: 3 After: Worker: 5, Min: 4, Max: 100, Idle: 4, Retired: 0, Suspended: 1, CPU(Avg): 100, CPU: 100 Finished in 00:00:36.4708368 Before: Worker: 5, Min: 4, Max: 100, Idle: 5, Retired: 0, Suspended: 0, CPU(Avg): 7, CPU: 0 After: Worker: 6, Min: 4, Max: 100, Idle: 5, Retired: 0, Suspended: 1, CPU(Avg): 100, CPU: 100 Finished in 00:00:36.2496669 Before: Worker: 6, Min: 4, Max: 100, Idle: 6, Retired: 0, Suspended: 0, CPU(Avg): 35, CPU: 0 After: Worker: 7, Min: 4, Max: 100, Idle: 6, Retired: 0, Suspended: 1, CPU(Avg): 100, CPU: 100 Finished in 00:00:36.2084714 Before: Worker: 7, Min: 4, Max: 100, Idle: 7, Retired: 0, Suspended: 0, CPU(Avg): 7, CPU: 0 After: Worker: 8, Min: 4, Max: 100, Idle: 7, Retired: 0, Suspended: 1, CPU(Avg): 100, CPU: 100 Finished in 00:00:36.8463683 Before: Worker: 0, Min: 4, Max: 100, Idle: 0, Retired: 0, Suspended: 0, CPU(Avg): 3, CPU: 0 After: Worker: 4, Min: 4, Max: 100, Idle: 3, Retired: 0, Suspended: 1, CPU(Avg): 100, CPU: 100 Finished in 00:00:37.0737835 1 - RSP-11267.patch
  10. Sorry if that is not clear. The license gives you the full source code. Yes, now I read this myself, it is bit confusing, I'll change it.
  11. Attila Kovacs

    SVG control package v2.3 update 4 released

    The prices were ok, I started scratching my head at this: "Delphi Source code of the SVG control package, this includes:" "The source code necessary to parse and render svg graphics" ...... I could not decide if one would get all the sources or partially just dcu's or whatever.
  12. Uwe Raabe

    MMX for Delphi 10.3 Rio

    I finally got hit by the problem myself and did some deeper investigation. It turned out that the freeze happens when System.pas was parsed in the background. It contains some constructs with conditional defines that are not handled well by the internal parser. Adding System to the list of excluded files avoids that. Then I made a complete scan over the available Delphi source files (at least those present on my development machine - alas, some platforms are missing) and found two other source files with the same problem: IdThreadSafe.pas and IdGlobal.pas. It would be great if those people affected by this problem can test this workaround and add System, IdGlobal and IdThreadSafe to the Excluded list.
×