Iterating devices and supported families

[gitkomodo]

Iterating all available devices can take a lot of time when there are multiple sensors on the 1-wire bus. The typical way to iterate all devices, also used in the library in both setResolution() functions, is with a for-loop like this:

DeviceAddress deviceAddress;
for (int i = 0; i < sensors.getDeviceCount(); i++) {
  sensors.getAddress(deviceAddress, i);
  [do something with the deviceAddress]
}

This way to iterate all devices takes a lot of time because the getAddress() function starts to look for devices from the start. Every time it is called, it finds the first device address first and keeps going until the device is found at the index asked for. Schematically:

1
1 2
1 2 3
1 2 3 4
1 2 3 4 5

The Onewire protocol and library make it possible to continue the first address search and win a lot of time, schematically:

1
> 2
  > 3
    > 4
      > 5

With five sensors on the 1-wire bus this way of continuing the search would save the time of 'finding' 10 addresses. This functionality can be added to the DallasTemperature library by adding these two functions, their names are consistent with the resetAlarmSearch() and alarmSearch() functions:

void DallasTemperature::resetAddressSearch(void) {
  _wire->reset_search();
}

bool DallasTemperature::addressSearch(uint8_t* deviceAddress) {
  if ( !_wire->search(deviceAddress) )
    return false;
  if ( !validAddress(deviceAddress) )
    return addressSearch(deviceAddress);
  return true;
}

The typical and faster way to iterate all devices using these functions becomes:

DeviceAddress deviceAddress;
sensors.resetAddressSearch();
while ( sensors.addressSearch(deviceAddress) ) {
  [do something with the deviceAddress]
}

The library could use resetAddressSearch() and addressSearch() in both setResolution() functions. I did some speed measurements changing the resolution 10 times with both the global and the one address setResolution functions. I started with the setResolution branche of Rob Tillaart which is optimized already on other aspects. For the measurements I turned of the AutoSaveScratchPad flag, toggled back and forth between resolution 10 and 11 for 5 times and had 3 sensors connected. These were the results:

Getting addresses by index >>
10x setResolution(global):  1513 ms
10x setResolution(address): 1452 ms

Searching next address >>
10x setResolution(global):  1079 ms (28.7% faster)
10x setResolution(address): 1018 ms (29.9% faster)

So the library can gain speed by using resetAddressSearch() and addressSearch(). Adding them as private functions would be a gain, but libary users may also be interested in using them. What is your opinion, should they be added as private or public functions, or not added at all?

---

Aside from speed there are additional problems in the (old) typical way to itterate all devices, also found in the library in both setResolution() functions:

• Forgot to check return value of getAddress(). In itself easy to add. It should be checked because the value returned by getDeviceCount() is reflecting the number of devices on the 1-wire bus when begin() was (last) executed. This number may be changed since that moment. The new way of itterating solves this problem.
• Forgot to check if the found address belongs to a device supported by the library. This can be checked with validFamily(). Intuitively one may think using getDS18Count() instead of getDeviceCount() in the for-statement would solve this, but that won't work as the indexes used in getAddress() also increase for unsupported devices.

I can think of two ways this last problem can be countered:

1. First, the library can be altered to only count supported deviced when indexes are used. Similarly, the addressSearch() function above would only find supported device families. Maybe a bit over the top would be to add validFamily() checks to every function sending a command to a device. With this the current behavior of the library is slightly altered, but maybe this is the way implementation was always meant to be?

2. Second, it is posible to add a flag to the addressSearch() function to indicate if all devices or all supported devices are needed. When this is preferred to the solution above, an additional question arrises: should the default be to find (a) all devices, or (b) all supported devices?

My personal order of preference would be (1) first, then (2b) and then (2a). What do you think?

---

While looking into the search code of the OneWire library I noticed it also supports the Conditional Search command that is used to search for devices in an 'alarmed' state. The DallasTemperature seems to use adapted code from an old version of the OneWire library in the alarmSearch() function. Since then there has probably been good reason to replace the code in the OneWire library 'by the one from the Dallas Semiconductor web site' (as is noted in the comments of the OneWire library).

I'm wondering if the separate search code for alarms in DallasTemperature is still needed. Using the standard capability in the OneWire library would reduce compiled size and there would be no need to declare global variables alarmSearchJunction, alarmSearchExhausted and alarmSearchAddress[] anymore. It may even not be needed to use REQUIREALARMS anymore. But maybe I'm not aware of reasons to duplicate the conditional search capability... What is your opinion on this?

[RobTillaart]

Part 1: loops to iterate over devices are O( n x (n-1) ) while it could be O(n)

You did an experiment with 3 devices, that means
1
1 2
1 2 3
6 steps == 151 ms

was replaced by
1
2
3
3 steps == 101 ms

==> every search saved == ~15 ms, IMHO a substantial gain.

[prediction 2 devices ==> 1 saved search == 15 ms]
[prediction 4 devices ==> 6 saved searches == 90 ms]

Public vs Private

The function sensor.getAddress() is public and used for quite some time. So the new functions must be made public too (same purpose)

Recursion
One point of attention is that addressSearch(deviceAddress) is recursive and on a microprocessor the stack and heap are already close enough :)

I propose to rewrite [ please verify ] - might gain a few micros too.

bool DallasTemperature::addressSearch(uint8_t* deviceAddress) {
	while (_wire->search(deviceAddress)) {
		if (validAddress(deviceAddress)) return true;
	}
	return false;
}

Addressing by index
Addressing the sensors by index is IMHO error prone as sensors or other one-wire devices may fail causing their "numbering" to change run time. Although I back the above proposal, it is not adequate to solve this issue. Think also of the scenario in which one sensor fails and is replaced by another one. The numbering will probably change.

To be sure to read the right sensor one must use its address. As this takes 8 bytes per sensor it uses a lot of space on a small processor. Therefor I proposed in the past to use the alarm fields as user data fields which makes it possible to use a single byte to address the right sensor, even when others are broken or replaced (with same user data field of course) .

Other addressing scheme?
I have been thinking of another addressing scheme to identify DS sensors. (not 100% fool proof but almost in most scenarios) It uses byte 7 [CRC] of the sensor address as the unique id of the sensor. It can have 256 unique values and even for up to 20 sensors it is still relative easy to find sensors with an unique ID/CRC. Advantage is that one does not need the alarm fields for unique ID.

A variation on this scheme uses 2 bytes of the 8 address bytes as identification. From my limited heuristics byte 1 seems a good candidate. Combined with the CRC this gives 65536 possible id's which makes the chance of address collision pretty small even up to 100 sensors.

Keeping one byte per sensor is not as memory consuming as keeping all 8 address bytes.
To make this work one should have a function like

bool getAddressFromCRC(uint8_t* address, uint8_t CRC)
{
  resetAddressSearch();
  while ( sensors.addressSearch( address ) ) {
    if (address [7] == CRC) return true;
  }
  return false;
}

so far my feedback, the other points I'll have to think about a bit more.

[RobTillaart]

While looking into the search code of the OneWire library I noticed it also supports the Conditional Search command that is used to search for devices in an 'alarmed' state. The DallasTemperature seems to use adapted code from an old version of the OneWire library in the alarmSearch() function. Since then there has probably been good reason to replace the code in the OneWire library 'by the one from the Dallas Semiconductor web site' (as is noted in the comments of the OneWire library).

I'm wondering if the separate search code for alarms in DallasTemperature is still needed. Using the standard capability in the OneWire library would reduce compiled size and there would be no need to declare global variables alarmSearchJunction, alarmSearchExhausted and alarmSearchAddress[] anymore. It may even not be needed to use REQUIREALARMS anymore. But maybe I'm not aware of reasons to duplicate the conditional search capability... What is your opinion on this?

If it is possible to keep the interface and at same time reduce /minimize the footprint is always a good idea...

IIRC REQUIREALARMS was used before there was an optimizing compiler, if functions are not called the compiler will not include them.

[gitkomodo]

Part 1: loops to iterate over devices are O( n x (n-1) ) while it could be O(n)
==> every search saved == ~15 ms, IMHO a substantial gain.

Public vs Private
The function sensor.getAddress() is public and used for quite some time. So the new functions must be made public too (same purpose)

Good to know you share my opinion. 👍

Recursion
One point of attention is that addressSearch(deviceAddress) is recursive and on a microprocessor the stack and heap are already close enough :)

I propose to rewrite [ please verify ] - might gain a few micros too.

Good to rewrite the recursion as a loop, I think the proposed code is correct.

Addressing by index
Other addressing scheme?

A lot to think about... I read earlier posts about this and will think about these points too.

AlarmSearch

If it is possible to keep the interface and at same time reduce /minimize the footprint is always a good idea...

By using the OneWire library search function for the conditional/alarm search too, the internal search variables will be shared with the normal/address searches. It will not actually change the interface, but a small part of behavior will change: because the search variables will be shared the alarmSearch will be reset whenever begin() or resetAddressSearch() is called.

IIRC REQUIREALARMS was used before there was an optimizing compiler, if functions are not called the compiler will not include them.

Apart from the functions there are some variables for every instance of DallasTemperature. I think they use memory even when the functions are not used. Setting the default/no alarmHandler in the constructor may also take some space. Compiling a sketch without searching alarms with REQUIRESALARMS == false shows a difference of 8 bytes in program storage space and a difference of 12 bytes in use of dynamic memory by global variables (Arduino Nano).

Sharing the search variables will probably decrease that memory usage. Not a substantial number of bytes (but a substantial part of the 12/8 bytes?), but the 'need' for setting REQUIRESALARMS to false will decrease even further.

[gitkomodo]

Just noticed that getAddress() checks the validity of an address only when it is at the requested index, but it does number devices with invalid addresses. I think only valid addresses should have an index, or even only valid addresses of supported devices. See my post/questions above.

[RobTillaart]

Addressing by index only works well if

1. there is only one type of device per bus
2. there are no failures on the bus
3. there are no (run time) replacements on the bus

Imagine the class scans the bus at start-up and compares the number of DS18B20 devices found that with a parameter of the constructor. This would guard pretty well against [2].
During this initial scan it also checks if there are other types of devices on the bus and their number. This would definitely help to handle [1].

If an DS18B20 address is requested by index, the class scans the whole bus again to see if the number of devices is the same. During the scan it of course saves the address @ index. If the full scan returns the same number of devices and no sensor is replaced one can be quite certain that the address is indeed the sensor intended.

To recognize (run time) replacement [3] the initial scan should not only count the devices, but also store a CRC16 of all individual addresses. If a device is replaced, chance is only 1 in 65536 that the new CRC16 will be identical. This is not 100% but acceptable, otherwise use CRC32. Even better is to have this CRC16 as parameter in the constructor too (for robustness sake) but that would mean that two instances of the system would have different code. But how much robustness is needed?

Extra memory would be a few bytes to hold the number of devices and the CRC16/32. And yes, some calls would take (quite a bit) longer as it would scan the bus completely.

just some thoughts...

[MalcolmBoura]

I have created another issue #193 which has considerable overlap with this and proposes a solution.