Unitrunker said:
A hash lookup would cost less than the effort to parse the OSW. Even if a hash map wasn't practical in terms of memory, a binary search would do just fine. A dozen iterations covers the entire ID space of a Type II system.
Rick, a few points to consider:
The ID space that a scanner has to cover isn't the valid Type II talkgroups (1 to 4000 or so); it's the ID's that the scanner will let you store, which are the "scanner talkgroups" 1 through 65535 plus radio ID's 1 through 65535 plus the wildcard (i700000).
Of course, a binary search is only concerned with how many sorted entries you're searching and a dozen iterations can handle 4096 entries, which I think most of us would be more than happy with (there's always someone looking for more...)
Problem is, unlike a PC-based decoder app, scanners let the users pick the order that talkgroups are stored in (or at least presented in). Keeping the list truly sorted while still presenting it to the user in the user's order would use more memory per system. You could probably do it by adding an extra field to each record to indicate where the record falls in the user's order. So the memory bite isn't huge, but the coding changes could be significant.
Further, are talkgroups actually stored in contiguous memory? If I add a new talkgroup to the first system in the scanner does it push everything in every other system down by few dozen bytes? Maybe it does - it takes long enough... If the data is really stored as a linked list with a pointer to the next (and previous?) record, binary searching isn't an option. I haven't actually looked in to this question, but aren't systems stored in some form of flash RAM where you wouldn't want to be rewriting large chunks of it every time something is added or deleted?
As you know, most problems can be addressed by throwing one or more of the following at them:
- 1: higher clock speed
- 2: more memory
- 3: more code (e.g. smarter algorithms, etc.)
1 isn't an option here. The hardware is already in our hands and higher clock speeds equals higher battery drain, perhaps a more expensive processor, etc.
2 is often an option on modern PC's, but not on a scanner that's limited to 1 MB or so for all stored systems. More memory could be added, but that raises the cost for every unit sold (I wouldn't mind paying an extra $25 though). So a hash-based approach really isn't ideal here.
That leaves number 3. But you can't go too crazy; management isn't going to OK a total rewrite. From what we've seen, the current firmware crop is designed to complete a talkgroup list scan in less time than it takes for the next OSW to fully arrive. Changing it so that some variable number of OSW's can be buffered while long searches complete may or may not be an easy task and the changes wouldn't be localized. For one, you would have to add the smarts to avoid checking every grant or late entry, since you'd risk never getting caught up - a big talkgroup list combined with a busy site would sink you.
Ideally, you'd come up with something that's simple, localized, and uses a fixed amount of data storage. I figure you could do that if you just wedged some small cache logic between the "OK, I have an ID; should I tune to it?" and the "Let me look that up for you." bits. I'd start with about 30 or so cache slots to store the status of recently looked up talkgroups or radio ID's. Each cache entry would need several fields:
- the ID (a talkgroup or radio ID)
- where it's stored (e.g. its actual address in memory; zero = entry doesn't exist)
- when this entry was last queried (this is for slot reuse - toss the least recently accessed). An 8 bit value should suffice here.
Now you still have to honour the "no more than 200 (or 250) lookups per OSW" limitation that currently exists, so one added wrinkle is that the "Let me look that up for you." code has to be told where to start in the list and it has to limit itself to no more that 200 checks per call and it has to return an addition result (e.g. list scan not completed).
The cache logic can handle this requirement by using that second field (the address field) to track the status of the list scan. E.g. a very small value (like 1 to 4) means that a partial scan has been done and the status of the given ID has not been determined yet. E.g. 1 = the first 200 have been scanned, so scan the next 200; 2 = the first 400 have been scanned, so check from 401 to 600, etc. As long as no talkgroup records are stored that low in memory (easy to force them higher anyway), there should be no problem.
So the first time an ID is seen, if it's not in the first 200 entries, the cache logic will return a "Don't tune to it (at this time)" result. 0.05 or 0.1 seconds later, when the ID is seen again in one of the copies of the call grant and the list scan completes, a definitive "it doesn't exist" or "here it is, figure out what you need to do" result is returned. Users would never notice the slight delay. Any further checks on the ID will not trigger a scan as the result is now cached (until that cache slot gets reused).
The above numbers are for a 246/396 processor. You can adjust them up for a 996 (250 vs 200, etc.)
If the user makes any edits (like adding/deleting/changing an ID), just wipe the entire cache. When the scanner switches to another trunked system, wipe the cache.
That pretty much covers it. There might be issues on systems with slow data rates (e.g. LTR), but I don't think there are very many LTR systems out there with 500+ group ID's. Even if there are, you have to look at the tradeoffs (a simple fix that helps most users vs a real fix that costs many programmer man hours). LTR monitors would have the option of programming important or common group ID's first anyway, so no worries.
I don't expect anything like this to be backported to the 246/396/996/etc., as it involves too many other changes (UASD, user manual, etc.), but it could be dropped in to the firmware for the next round of scanners they offer up, so I ain't buying any "we can only handle 250 (or 300) talkgroups per system" claims.
Just thinking out loud here, but I have to wonder if they've fully optimized their existing talkgroup scanning code. As I understand it, the firmware is probably written in C or something similar. Have time-critical portions like this been written in tight assembler code? I wonder...
